B. Bicycle in Ibirapuera
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Carlos loves to ride his bicycle in Ibirapuera Park, just like many people from São Paulo, but he doesn't like when the park is too crowded, making it difficult for him to enjoy his ride. On a map of the park that Carlos found, the park is described as having $$$N$$$ different locations connected by $$$M$$$ paths of varying distances, and Carlos verified that it is possible to go from any point in the park to any other using these paths.

Carlos's life changed when he started working in the park, and as a benefit of working there, he can ride his bicycle before the park opens, allowing him to enjoy the entire park while it is empty.

Carlos is on his day off and wants to take a bike ride from location $$$1$$$ to $$$N$$$, but he does not want to pass through any location that already has people there. When the park opens, numerous people start entering through $$$K$$$ different entrances. Once the people enter, they begin to use all possible paths to go to all locations. If the distance of a path is $$$D$$$, it takes people $$$2D$$$ minutes to walk the entire path. Carlos, on the other hand, has double the speed of the people, meaning he takes $$$D$$$ minutes to complete a path of distance $$$D$$$ on his bicycle.

With this in mind, Carlos is interested in knowing the minimum time he needs to leave from location $$$1$$$ before the park opens so that there is a way to reach point $$$N$$$ without passing through any location that already has people. During the journey, Carlos can arrive at some of the park's locations at the same moment as the people, but if the people arrive before Carlos, he can no longer pass through that location on his way.

Input

The first line contains 3 integers, $$$N$$$, $$$M$$$, and $$$K$$$ $$$(2 \le N \le 10^5, N - 1 \le M \le 10^5, 1 \le K \le N)$$$. The next $$$M$$$ lines each contain 3 integers $$$A$$$, $$$B$$$, and $$$C$$$, indicating that there is a path between locations $$$A$$$ and $$$B$$$ with distance $$$C$$$ $$$(A \ne B$$$ and $$$1 \le A,B \le N$$$ and $$$1 \le C \le 20000)$$$. The paths can be used to go from $$$A$$$ to $$$B$$$ as well as from $$$B$$$ to $$$A$$$, and there is only one path between each pair of locations.

The last line contains $$$K$$$ distinct integers indicating which $$$K$$$ locations have an entrance that people enter as soon as the park opens.

Output

Output a single integer indicating the smallest non-negative integer time in advance that Carlos needs to start his journey from location $$$1$$$ and reach location $$$N$$$ in such a way that there is a possible path without passing through any location with people.

Examples
Input
2 1 1
1 2 10
2
Output
10
Input
4 3 1
1 2 40
2 3 10
2 4 30
3
Output
20
Input
5 4 3
1 2 10
5 2 10
3 2 6
4 5 15
1 4 3
Output
0
Note

Explanation of example 1:

Carlos needs to start at location $$$1$$$ with $$$10$$$ minutes in advance before the park opens. This way, he can arrive at location $$$2$$$ exactly when the park opens and the people enter. If he leaves with $$$9$$$ minutes in advance, the people will arrive at location $$$2$$$ before Carlos, and thus he will not be able to complete his journey.

Explanation of example 2:

Carlos needs to start at location $$$1$$$ with $$$20$$$ minutes in advance before the park opens. This way, he can reach the halfway point between location $$$1$$$ and $$$2$$$ when the park opens. When the park opens, people enter through location $$$3$$$ and arrive at location $$$2$$$ after twenty minutes, and Carlos also arrives at the same time. After that, since Carlos is faster than the people, he can reach location $$$4$$$ before the people arrive. If Carlos leaves with less than $$$20$$$ minutes in advance, the people will arrive at location $$$2$$$ before him, and Carlos will have no path to reach location $$$4$$$.

Explanation of example 3:

Carlos can start riding his bicycle as soon as the park opens, leaving location $$$1$$$ at time $$$0$$$, arriving at location $$$2$$$ at time $$$10$$$ minutes, and reaching the final location $$$5$$$ at time $$$20$$$ minutes, while the people will arrive at location $$$1$$$ at time $$$0$$$, at location $$$2$$$ at time $$$12$$$ minutes, and at location $$$5$$$ at time $$$30$$$ minutes.