시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 512 MB 0 0 0 0.000%

문제

You are Nilan, the marathon organiser of the country Berapur. There are N cities in the country, connected by M roads. The cities are indexed from 1, 2, . . . , N each road is indexed from 1, 2, . . . , M. The ith road directly connects city ui with city vi, and it takes wi seconds to travel on this road. The roads are bidirectional in nature and it is also ensured that there are no selfloops or multi-edges in the road network. Out of the N cities, there is a list of K distinct cities A1, A2, . . . , Ak which are special.

As the marathon organiser, you are going to try to organise a relay marathon. A relay marathon is defined as follows: 2 groups of people are present at the starting cities start1 and start2 respectively. Firstly the people from start1 travel to finish1. Once the first group reaches finish1, then immediately (i.e without any delay), the second group of people start travelling from start2 to finish2. Once the second group reaches finish2, the relay marathon ends. Do note that a relay marathon is valid only if start1, finish1, start2 and finish2 all are special and distinct from one another.

Let D(a, b) denote the shortest time to travel from city a to city b in the above road network. In case there is no path from city a to city b, then let us define D(a, b) = ∞. Then the total time taken in such a valid relay race is defined as D(start1, finish1) + D(start2, finish2).

Given this, your job is to find the minimum possible value of D(start1, finish1) + D(start2, finish2) amongst all valid tuples (start1, finish1, start2, finish2).

Note: In the input network of roads, it will always be ensured that there are exists at least one valid tuple of four distinct cities, (a, b, c, d), such that a, b, c, d all are special and D(a, b) + D(c, d) < ∞ (i.e there exists a path from city a to city b and another path from city c to city d.)

입력

Your program must read from standard input.

The first line of the input contains 3 integers, N M K denoting the number of cities, the number of roads and the number of special cities respectively.

M lines will follow. Each consisting of 3 integers ui vi wi, meaning that there is a road between city ui and city vi which takes wi seconds to travel in either direction.

The next line contains K distinct integers A1, A2, . . . , Ak denoting the list of special cities.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the optimal minimum value of D(start1, finish1) + D(start2, finish2) (in seconds).

제한

  • 4 ≤ K ≤ N ≤ 105
  • 2 ≤ M ≤ min(N(N−1)/2 ,3 × 106)
  • 1 ≤ wi ≤ 1000 for all 1 ≤ i ≤ M
  • 1 ≤ ui ≠ vi ≤ N for all 1 ≤ i ≤ M

예제 입력 1

5 4 4
1 2 1
3 4 2
4 5 5
5 3 8
3 1 5 2

예제 출력 1

8

The cities in grey denote the special cities. We can observe that D(1, 2) = 1 and D(3, 5) = min(8, 2 + 5) = 7. The optimal pairing here is D(1, 2) + D(3, 5) = 1 + 7 = 8 (i.e start1 = 1, finish1 = 2, start2 = 3 and finish2 = 5), any other kind of pairing configuration of {3, 1, 5, 2} will not be better than this.

예제 입력 2

6 6 4
1 2 5
2 4 7
4 6 50
6 5 3
1 5 15
3 5 6
1 5 4 6

예제 출력 2

15

The cities in grey denote the special cities. We can observe that D(1, 4) = 5 + 7 = 12 and D(5, 6) = 3. The optimal pairing here is D(1, 4) + D(5, 6) = 12 + 3 = 15 (i.e start1 = 1, finish1 = 4, start2 = 5 and finish2 = 6), any other kind of pairing configuration of {1, 4, 5, 6} will not be better than this.