You are given n cities with m bi-directional roads connecting them and the length of each road. There are two friends living in different cities who wish to collect some ingredients available at different stores to make cake. There are s such stores. They need not come back home after purchasing the ingredients. Petrol is expensive and they would hence like to travel minimum total distance (sum of distance distance travelled by both kids). Help them find out what this distance is.

Input

n m
(m lines of the form a_i b_i c_i)
Here n is number of cities, m is number of roads, a_i and b_i are the cities (0 indexed) the roads connect and c_i is the length of this road
s where s is the number of stores
(1 line containing s space separated integers indicating the city number in which the stores are located.)
(two space separated integers indicating the cities in which the two kids live)

Output

Single integer x where x is the minimum distance that the duo will travel that is minimum sum of distance travelled by first kid and second kid.

Constraints:

2 ≤ n ≤ 100
1 ≤ m ≤ (n * (n - 1)) / 2
0 ≤ a, b < n
0 ≤ c ≤ 1000
1 ≤ s ≤ 8

Sample

Input:
5 6
0 1 5
1 4 1
0 4 10
0 2 2
1 2 3
2 3 4
2
2 4
0 1

Output:
3

Problem Setter: Vidit Gupta