flights

Problem Description

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 P_i. 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 A_i to another, B_i, (one-way) and cost a certain amount of money C_i. 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.

Input

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 P_i.
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 A_i, B_i, C_i.

Output

The output should contain one line with one integer, the maximum amount of revenue Peanut can earn.

Limits

All airfare will be under $10 000.
All cities will have population under 1 000 000.
Subtask 1 (13%): 1 ≤ N, E ≤ 100. All airfare <= $10.
Subtask 2 (21%): 1 ≤ N, E ≤ 1 000.
Subtask 3 (25%): 1 ≤ N, E ≤ 100 000. If there is a direct or indirect route from city X to city Y, there will not be a direct or indirect route from city Y to city X.
Subtask 4 (41%): 1 ≤ N ≤ 100 000. 1 ≤ E ≤ 500 000.
Subtask 5 (0%): Sample testcases.

Sample Input 1

4 3
3 2 2 1
1 3
1 2 3
2 3 5
3 0 1

Sample Output 1

16

Sample Input 2

4 4
3 2 1 7
2 1
0 2 7
2 3 4
3 1 5
1 0 5

Sample Output 2

9

Sample Input 3

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

Sample Output 3

20