問題文

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

入力

$NML$
$t_1\cdots t_N$
$a_1{b}_1{c}_1$
$⋮$
$a_m{b}_m{c}_m$

$2\le N\le 2000$
$N-1\le M\le 2000$
$0\le t_i\le 2000$
$1\le \sum t_i$
$1\le L,a_i,b_i\le N$
$1\le c_i\le {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