The National University of Singapore is built on a hill, so even if the distance from A to B seems short from the map, walking over the steep ladder is very exhausting. Fortunately, there's a shuttle bus service.
Suppose that NUS has \(N\) buildings and \(E\) bidirectional roads. A shuttle bus starts moving from building X to building Y (the detailed path will be given). At the same time, Chris starts walking from building A and wants to go to building B. Chris is as fast as the shuttle bus, but walking \(k\) meters requires \(k\) amount of energy (in Joules) while no energy is spent if he travels by a shuttle bus. What is the minimum amount of energy will Chris need to arrive at his destination?
Details and Assumptions
Input Format
The first line consists of two integers \(N\), \(E\)  the number of buildings and the number of bidirectional roads.
The next \(E\) lines each contains 3 integers \(u, v, t\) describing a bidirectional road connecting building \(u\) and \(v\) of length \(t\).
The next line contains an integer \(M\), the number of buildings the shuttle bus go through.
The next line contains \(M\) integers, describing the path of the shuttle bus in that order.
The last line contains two integers \(A\) and \(B\), the starting building and the destination respectively.
Sample Input
1 2 3 4 5 6 7 8 9 

Sample Output
1 

Problem Loading...
Note Loading...
Set Loading...