Minimum Pairwise Shortest Path Among Special Cities

J country has \(n\) cities connected by \(m\) directed roads, each with a given length. Rainbow once invited Vani to visit. However, Vani is only interested in \(k\) cities that have a long history and unique natural scenery. To enhance his travel experience, Vani wants to know the minimum value among all the shortest paths computed between every ordered pair of these \(k\) special cities. In other words, among all pairs \((i, j)\) (with \(i \neq j\)) of special cities, find the minimum \(d(i,j)\) where \(d(i,j)\) represents the shortest path from city \(i\) to city \(j\). If no path exists between any two special cities, output -1.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line of input contains three integers \(n\), \(m\), and \(k\), representing the number of cities, the number of directed roads, and the number of special cities, respectively. The next \(m\) lines each contain three integers \(u\), \(v\), and \(w\), indicating there is a directed road from city \(u\) to city \(v\) with length \(w\). The last line contains \(k\) distinct integers representing the indices of the special cities Vani is interested in.

outputFormat

Output a single integer representing the minimum shortest path distance between any two distinct special cities. If no such path exists between any two special cities, print -1.

sample

4 4 2
1 2 3
2 3 2
1 3 10
4 3 1
1 3

5