Road Trip

Denis was lucky and won free refueling at Oyster petrol stations in a lottery. He is fond of the idea to go on his motorcycle across the country, starting in his hometown on the west and ending in the capital city on the east. He must plan the route carefully, Oyster petrol stations are located only in some cities and Denis does not want to pay anything for petrol. He also does not want to take any additional canister, so fuel has to be pumped to the motorcycle tank only. He considers to drive on highways. Each highway connects two cities, hence there are no crossroads outside cities. Denis prefers to select one of the shortest possible routes. Oyster is present in the hometown as well as in the capital city. It is assumed that fuel consumption is proportional to the traveled distance.



Image 1. Example of the cities and the highways layout together with the highway lengths. Doubled circles denote cities where Oyster is present. Assuming the motorcycle maximal driving distance without refueling is 10, the green lines follow the shortest travel route of length 19 from the hometown 0 to the capital city 7.

The task

You are given the list of highways connecting cities together with their lengths, the list of cities with Oyster petrol stations and the motorcycle range on a full tank. Find the length of the shortest possible route from the hometown to the capital city.

Input

The input consists of more text lines. The first line contains six integers M, N, H, F, S, T separated by space. M is the number of cities with Oyster, N is the number of cities without Oyster, H is the number of highways, F is the motorcycle maximal driving distance without refueling, S is the label of the hometown and T is the label of the capital city. We suppose all the cities to be labeled by integers 0, 1, 2, ... M+N−1. Next, there are M lines that represent an enumeration of all cities with Oyster. Each of the lines contains a city label. Finally, there are H lines representing highways. Each line contains three integers x, y, d separated by space. Values x and y are labels of two cities connected directly by a highway of length d.
The value of M does not exceed 15000, the value of N does not exceed 105 and the value H does not exceed 200000. It is guaranteed that some suitable route always exists.

Output

The output contains one text line with single integer representing the length of the shortest route. The output value can be stored in 31 bits.

Example 1

Input
6 2 9 10 0 7
0
2
3
4
5
7
0 1 5
1 2 1
2 3 5
4 5 5
5 6 1
6 7 5
0 4 9
1 6 5
3 7 9
Output
19
The scheme of the input and the layout of the optimal route are depicted in the Image 1.

Example 2

Input
3 1 5 15 0 3
0
2
3
0 1 10
0 2 14
1 2 3
1 3 10
2 3 14
Output
26




Image 2. The cities and the highways layout together with the highway lengths specified in Example 2. The motorcycle driving distance is 15. The optimal route from the hometown 0 to the capital city 3 has length 26.

Example 3

Input
4 3 8 10 0 5
0
1
2
5
0 3 6
0 2 7
0 1 6
1 4 5
2 6 3
3 5 6
4 5 4
6 5 3
Output
13





Image 3. The cities and the highways layout together with the highway lengths specified in Example 3. The motorcycle driving distance is 10. The optimal route from the hometown 0 to the capital city 5 has length 13.

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set

An additional public data set:
Link to public data set 2