Problem Statement

The country of tatyam has $N$ intersections numbered from $1$ to $N$ and $M$ roads connecting them; intersection $a_i$ and intersection $b_i$ are connected by a road of length $c_i$.
A festival is held in the country of tatyam, and at the festival trucks may be rotated by 90 degrees. In preparation for the upcoming festival, tatyam plans to gather the trucks at a single intersection.
tatyam owns one tow truck, and the tow truck can lift and carry one truck.
The tow truck is parked at intersection $L$, and $t_i$ trucks are parked at intersection $i$.
Find the travel distance when the tow truck is moved with the shortest possible travel distance so that all trucks are gathered at a single intersection.

Input

$N\ M\ L$
$t_1\ \cdots\ t_N$
$a_1\ b_1\ c_1$
$\vdots$
$a_m\ b_m\ c_m$

$2\leq N\leq 2000$
$N-1\leq M\leq 2000$
$0\leq t_i\leq 2000$
$1\leq\sum t_i$
$1\leq L,\ a_i,\ b_i\leq N$
$1\leq c_i\leq 10^6$
The graph formed by the given intersections and roads is connected.

Output

Output the travel distance when the tow truck is moved with the shortest possible travel distance so that all trucks are gathered at a single intersection.
If the trucks are already at a single intersection, output 0.
Print a newline at the end.

Sample

4 3 1
0 1 1 1
1 2 1
1 3 2
1 4 3

12

5 5 1
0 2 1 1 2
1 2 1
1 3 2
2 4 2
3 4 2
4 5 2

19

7 9 1
1 1 1 1 1 1 1
1 7 3
2 3 3
2 5 4
3 4 5
3 5 1
3 7 6
4 6 2
5 6 7
6 7 9

53