問題文

tatyam国には $1$ 番から $N$ 番までの $N$ 個の交差点とそれらをつなぐ $M$ 本の道路があり、交差点 $a_i$ と交差点 $b_i$ が長さ $c_i$ の道路で繋がっています。
tatyam国では祭りが行われ、そこでトラックが90度回転することがあります。 tatyamは今度の祭りに備え、トラックを1つの交差点に集めようと考えています。
tatyamは1台のレッカー車を持っており、レッカー車は1台のトラックを持ち上げて運ぶことができます。
レッカー車は交差点 $L$ に停まっていて、交差点 $i$ には $t_i$ 台のトラックが停まっています。
レッカー車をできるだけ短い移動距離で動かして全てのトラックを1つの交差点に集める時、その移動距離を求めてください。

入力

$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$
与えられる交差点と道路でできるグラフは連結である

出力

レッカー車をできるだけ短い移動距離で動かして全てのトラックを1つの交差点に集める時、その移動距離を出力してください。
すでにトラックが1つの交差点にある場合は 0 を出力してください。
最後に改行してください。

サンプル

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