In the world of Wynncraft, it is essential to know how to get around quickly. If you don't use Wynntils, it is quite difficult to get around the world map if you don't know the way to get there. Fortunately for you, there are quick travels that can send you from 1 place to another instantly (for the purposes of this question every fast travel is instant, and the V.S.S. Seaskipper doesn't count as a fast travel). Of course, Wynncraft also has a 3rd way to get around - travel scrolls, and you have ~S~ of them. At the cost of 1 soul point, you can teleport instantly to one of the ~T~ towns or cities with their corresponding travel scroll, no matter where you are. Unfortunately, you have no soul points left since you died 6 times in the Qira Hive. But, luckily for you, the sun rises in ~R~ seconds, giving you a precious soul point, enabling you to use 1 travel scroll. Plus, you don't have travel scrolls to all available towns and cities anyway, you just have a few here and there from your time leveling up.

Your party member is located in town ~N~ and you are currently in town ~M~. There are ~F~ fast travels on the map. Find the minimum amount of time, in seconds, to get to your party member.

Constraints

~1 \leq T \leq 1000~

~1 \leq M,N,F \leq T~

~1 \leq S < T~

~0 \leq R \leq 1199~

Input Specifications

The first line will contain space-separated integers, ~M,N,R,T,S,F~.

The next ~\frac{T(T-1)}{2}~ lines will contain a pair of towns/cities, and then the time it takes to travel between them, in seconds. All pairs of towns/cities will appear exactly once. It will take at most ~10^4~ seconds to travel.

The next ~F~ lines will contain two towns/cities, indicating a fast travel exists between them.

The next ~S~ lines will contain a single town/city, a travel scroll you own.

Output Specifications

Determine the minimum amount of time, in seconds, it takes for you to reach town ~N~ from town ~M~.

Sample Input 1

2 4 10 4 1 1
1 2 6
1 3 4
1 4 5
2 3 7
2 4 13
3 4 8
3 4
1

Sample Output 1

7

Explanation for Sample Case 1

The quickest route is to spend 7 seconds travelling to town 3, before using the quick travel between 3 and 4 to arrive at town 4.

Sample Input 2

1 2 15 4 1 1
1 2 20
1 3 16
1 4 17
2 3 15
2 4 19
3 4 14
2 3
2

Sample Output 2

15