Under construction

Still being built. Things may change

Reckless Speleologists

Interview

Time limit1sMemory limit1024 MB

Summary
Find the fastest route from the start station to the exit, reaching each station strictly before smoke spreading from the campfires does.
Level

Medium5 of 10

Topics
Graph, Shortest path
Solved
No attempts yet

Problem

One day a group of speleologists set out to explore the caves of Africa. After going quite deep, they noticed something strange: the air smelled of smoke. "Could we have reached a volcano?" asked a newcomer in surprise. "No. Near a volcano it smells of sulfur," the captain replied. "Who was in charge of putting out the campfires?" Everyone shrugged uncertainly. "Well, friends, we are trapped."

The captain now faces a difficult task: how to lead the team out of the cave without suffocating. In speleologists' terms, a cave consists of many tunnels and stations. Each tunnel connects a pair of different stations and has its own length. The captain has a map of the cave, knows where the team lit campfires, and knows where the exit is.

Smoke spreads 1 meter per second. A tunnel of length kk adjacent to a smoky station fills with smoke in kk seconds, and the station at its other end fills with smoke as well. If the speleologists are at a station containing smoke, they suffocate. The speleologists run at 1 meter per second. Tunnels can be traversed in both directions. Initially, smoke is present only at the stations where the speleologists lit campfires. If the speleologists arrive at a station at the same moment the smoke does, they suffocate (this also applies to the exit station). It is guaranteed that the speleologists start at a station with no smoke.

Input

The first line contains three integers NN, MM, and KK: the number of stations, the number of tunnels, and the number of stations with campfires, where 2≤N≤2×1052 \le N \le 2 \times 10^5, 0≤M≤2×1050 \le M \le 2 \times 10^5, and 1≤K<N1 \le K < N. The second line contains KK distinct integers aia_i (1≤ai≤N1 \le a_i \le N), the stations with campfires. Each of the next MM lines contains three integers xix_i, yiy_i, and lil_i, meaning the ii-th tunnel connects stations xix_i and yiy_i and has length lil_i meters, where 1≤xi,yi≤N1 \le x_i, y_i \le N, xi≠yix_i \ne y_i, and 1≤li≤1091 \le l_i \le 10^9. The last line contains two integers SS and FF (1≤S,F≤N1 \le S, F \le N): the station where the speleologists are now, and the station of the exit.

Output

Print one integer, the minimum number of seconds the speleologists need to get out of the cave, or -1 if they cannot get out.

Examples2

  1. Example 1

    Input
    6 5 1
    6
    1 2 20
    2 3 2
    3 4 1
    2 5 1
    5 6 3
    4 1
    
    Expected output
    23
    
  2. Example 2

    Input
    6 6 2
    4 1
    4 1 1
    6 5 1
    2 4 1
    1 5 2
    5 6 2
    5 1 2
    3 6
    
    Expected output
    -1