The Annual Mega Super Awesome Grand Party is being held in Legumeland again. Legumeland is made of N cities spread out all across Legumeland, each numbered from 0 to N-1. Each city in Legumeland has a population of Pi. For the Annual Mega Super Awesome Grand Party, everyone in Legumeland has to travel to city 0 for the party. As a result, airlines have started organising a total of E flights that travel from one city Ai to another, Bi, (one-way) and cost a certain amount of money Ci. For purposes of saving cost, every person in Legumeland will pick the route of least cost to travel to city 0 for the Annual Mega Super Awesome Grand Party.
Peanut Airlines, keen to bring in profits, has planned a flight from city X to city Y. However, Peanut is unsure as to how much to price the airfare to maximise his revenue, his revenue being = cost of flight * number of people who travel on it. Help Peanut determine what is the maximum amount of revenue he can earn. To clarify, if a person has to choose between two routes of the same cost, one passing through Peanut Airlines' flight and one not, he will choose the one with Peanut Airlines due to its superior service. It is guaranteed that it is possible to visit city 0 from any city with usual flights only.
The first line of input will contain two integers, N and E.
The second line of input will contain N integers, with the ith integer representing Pi.
The third line of input will contain two integers, X and Y.
The next E lines of input will contain three integers each, with the ith line containing Ai, Bi, Ci.
The output should contain one line with one integer, the maximum amount of revenue Peanut can earn.
4 3 3 2 2 1 1 3 1 2 3 2 3 5 3 0 1
4 4 3 2 1 7 2 1 0 2 7 2 3 4 3 1 5 1 0 5
6 7 3 2 6 5 1 3 4 1 5 4 4 5 3 7 4 3 8 3 1 2 4 2 3 2 1 3 1 0 6