Distance#1638
In a large city, a mobile operator is organizing a competition among its subscribers to promote their new "pedestrian navigator" service. The main prize will be awarded to the first pair of subscribers who meet each other. The competition ends as soon as any such meeting occurs.
At the start of the competition, all subscribers are at their starting positions. It is known that they can see each other on their smartphones and move only on pedestrian paths at a constant speed of km/h. Each subscriber aims to win the prize and is indifferent to the others.
To organize the award ceremony, the mobile operator wants to know the minimal amount of time after which the competition will end.
The first line contains three integers , , and — the number of subscribers (2 \leq N \leq 10^5), the number of junctions (1 \leq K \leq 10^5), and the number of pedestrian paths in the city (1 \leq L \leq 10^5).
Each of the next lines contains a single integer S_i (1 \leq S_i \leq K) — the initial position of each subscriber (the junction in the transport network).
Each of the next lines contains three integers B_i, C_i, and D_i separated by spaces, indicating that there is a bidirectional pedestrian path between junctions B_i and C_i (1 \leq B_i, C_i \leq K, B_i \neq C_i) with a length of D_i (1 \leq D_i \leq 5000) kilometers.
Output the minimal possible number of minutes that may pass before the competition ends.
It is guaranteed that at least one pair of subscribers will meet.
Example 1