**15 人解决**，20 人已尝试。

**29 份提交通过**，共有 127 份提交。

**5.3** EMB 奖励。

**单点时限: **5.0 sec

**内存限制: **256 MB

In a large city a cellular network operator is holding a competition for subscribers to promote their new “pedestrian navigator” service. The main prize will be awarded to the first pair of subscribers to meet each other. The competition ends when any such meeting takes place.
At the start of the competition all the subscribers are at their known positions, are able to see each other on their smartphones, and are moving at a constant speed of 10 km/h taking only pedestrian walks. Each subscriber is willing to win the prize and is indifferent to the others.

In order to prepare for an award ceremony the cellular network operator needs to know the minimal amount of time after which the competition may come to an end.

In the first line of input integers N, K, and L are given — the number of subscribers in a cellular network company (2 ≤ N ≤ 10^{5}), the number of junctions (1 ≤ K ≤ 10^{5}), and the number of pedestrian walks (1 ≤ L ≤ 10^{5}) in the city, respectively.

On the next N lines of input S_{i} (1 ≤ S_{i} ≤ K) numbers are given — initial positions of subscribers (in the terms of transport graph junctions).

The next L lines of input pedestrian paths are given in the form of integers B_{i}, C_{i} and D_{i} separated by spaces. Each line denotes that there is a two-way pedestrian path between junctions B_{i} and C_{i }(1 ≤ B_{i},C_{i }≤ K, B_{i }!= C_{i}) with a length of Di (1 ≤ D_{i }≤ 5000) kilometers.

Output the minimal possible number of minutes that may elapse from the start till the end of the contest. It is guaranteed that at least one pair of the subscribers can meet.

Input

2 2 1 1 2 1 2 5 3 3 3 1 2 3 1 2 4 3 2 4 3 1 4 2 3 3 1 2 1 2 9 3 2 5 1 3 3

Output

15 12 24

**15 人解决**，20 人已尝试。

**29 份提交通过**，共有 127 份提交。

**5.3** EMB 奖励。

**创建**: 9 年，5 月前.

**修改**: 3 年，2 月前.

**最后提交**: 9 年，3 月前.

**来源**: N/A

题目标签