Problem Background

Original simulation question T2 for NOIP2018.

Difficulty level of T2 on DAY1 or DAY2 of NOIP.

Adapted from the novel "Harry Potter and the Chamber of Secrets."

Problem Description

The Chamber of Secrets has been opened.

Harry and Ron have entered the Chamber, which consists of \( n \) rooms, numbered \( 1, 2, \ldots, n \). There are \( m \) passages connecting these rooms, with at most one passage between any two different rooms, and each passage takes \( C_i \) time to traverse.

Initially, both Harry and Ron are in room \( 1 \). Their goal is to rescue Ginny and find the diary, but they realize that Ginny and the diary might be in two different rooms. To uncover the truth as quickly as possible, they decide to reach the two target rooms in the shortest time possible. However, some rooms can only be accessed by someone who can speak to snakes, which means only Harry can enter them.

Now, Harry tells you the structure of the Chamber. Please calculate the shortest time for them to reach the two target rooms.

Input Format

The first line contains \( n, m, k \), representing the number of rooms, the number of passages, and the number of rooms that only Harry can enter, respectively.

The second line contains \( k \) numbers, representing the room numbers that only Harry can enter. (If \( k = 0 \), this line is omitted.)

The next \( m \) lines each contain three numbers: \( a, b, c \), indicating that there is a passage between room \( a \) and room \( b \) that takes \( c \) time to traverse.

The last line contains two numbers \( x, y \), representing the room numbers that Harry and Ron need to go to.

Output Format

Output a single number, representing the shortest time to reach the two rooms.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5

Sample Input #2

10 13 3
3 4 10
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
6 7 10
7 8 5
8 9 10
9 10 3
10 1 2
1 9 6
3 8 10
4 6 3
6 8

Sample Output #2

16

Notes

Sample Explanation:

Sample One:

Harry: \( 1 \rightarrow 5 \rightarrow 6 \) with a time cost of \( 5 \).

Ron: \( 1 \rightarrow 3 \rightarrow 4 \) with a time cost of \( 5 \).

Thus, the shortest time is \( 5 \).

Sample Two:

As shown in the figure, orange represents the target rooms, and green represents rooms that only Harry can pass through.

Harry: \( 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 6 \) with a time cost of \( 9 \).

Ron: \( 1 \rightarrow 9 \rightarrow 8 \) with a time cost of \( 16 \).

Thus, the shortest time is \( 16 \).

Data Range:

\( 10\% \) of the data satisfies: \( n \leq 5 \).

\( 30\% \) of the data satisfies: \( n \leq 20 \).

\( 50\% \) of the data satisfies: \( n \leq 1000 \).

\( 70\% \) of the data satisfies: \( n \leq 10000 \).

\( 100\% \) of the data satisfies: \( n \leq 50000 \); \( a, b, k \leq n \); \( c \leq 1000 \); \( m \leq 100000 \), ensuring that Ron can reach room \( 1 \).

Special Conditions:

\( 30\% \) of the data satisfies: \( k = 0 \).

见题面 Input 部分

见题面 Output 部分