Whisker Bells

Time limit: 3000 msMemory limit: 256 MB

Gats is walking through a city with $N$ crossings and $M$ two-way alleys. The crossings are numbered $1, 2, \ldots, N$ . Each alley has a positive walking time and one bell tone from $1$ to $C$ .

At any moment, Gats remembers the tone of the last alley he walked through. He refuses to leave a crossing through an alley with the same tone as the one he remembers. If there is a milk fountain at the crossing, he forgets the remembered tone before choosing the next alley. At the start, he remembers no tone.

A walk may visit crossings and alleys more than once. Find the minimum total walking time for Gats to get from crossing $S$ to crossing $T$ .

Input

The first line contains integers $N$ , $M$ , $C$ , $S$ , and $T$ ( $1 \le N \le 2 \times 10^5$ , , , and ), the number of crossings, the number of alleys, the number of possible bell tones, the starting crossing, and the target crossing. The second line contains an integer (), followed by distinct integers , the crossings with milk fountains. For each with , . If , this line contains only the integer . The next lines describe the alleys. For each with , the -th of these lines contains integers , , , and (, , , and ). This means there is a two-way alley between crossings and with walking time and bell tone . There may be more than one alley between the same two crossings. All tokens are separated by spaces.

Output

Print one line containing a single integer. If at least one valid walk from $S$ to $T$ exists, this integer must be the minimum possible total walking time. Otherwise, print $-1$ .

Samples

Sample 1

Input

Output

The walk $1 \to 2 \to 3 \to 4$ has bell tones $1, 1, 2$ . The repeated tone $1$ is allowed because crossing has a milk fountain.

Whisker Bells

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2