First Pair to Meet

ACM Telecom is running an event to promote its new app, "Meeting Route". The first two people who meet through the app get a prize.

Right before the event starts, everyone knows where everyone else is from the app. Once two people decide to meet, they start at the same moment and move toward each other along the shortest route the app gives them. Everyone moves at 10 km/h. If the shortest route between two people is $d$ km long, each of them covers $d/2$ km and then they meet.

To prepare the award ceremony, ACM Telecom needs the smallest time the event can take. Given the positions of the people when the event starts and the map of the area, compute that time.

The first line contains the number of participants $N$, the number of vertices $K$ on the map, and the number of roads $L$ joining the vertices. ($2 \le N \le 100000$, $1 \le K \le 100000$, $1 \le L \le 100000$)

Each of the next $N$ lines contains one number $S_i$, the position of a person. ($1 \le S_i \le K$) It means person $i$ stands at vertex $S_i$. Several people may stand at the same vertex.

Each of the next $L$ lines describes one road as $B_i$, $C_i$, $D_i$. ($1 \le B_i \ne C_i \le K$, $1 \le D_i \le 5000$) It means there is a road of length $D_i$ km between vertex $B_i$ and vertex $C_i$. Roads can be travelled in both directions, and the same two vertices may be joined by more than one road.

Print one integer, the shortest time in minutes it takes for some two people to meet. At least one pair of people can reach each other. Two people who start at the same vertex meet at once, so the answer can be 0.