問題文

yukicoder王国には都市 $1$ から都市 $N$ までの $N$ 個の都市と、$M$ 本の道路があります。
都市 $i(1\le i\le N)$ の人口は $A_i$ です。$i(1\le i\le M)$ 本目の道路は都市 $X_i$ と $Y_i$ を双方向に結び、その長さは $Z_i$ です。
王国の任意の $2$ つの都市間は、いくつかの道路を通って双方向に行き来可能です。

ansain国王は順番に $K$ 個の都市に発電所を建設することにしました。
$1$ 個目の発電所を建設するときのコストは都市 $i$ に建設するとき、$A_i$ かかります。
$2$ 個目以降の発電所については、都市 $i$ に建設するとき、$A_i$ に加えて、都市 $i$ から最も近い建設済みの発電所がある都市までの距離のコストがかかります。
ただし、都市 $i,j$ 間の距離は、都市 $i$ から都市 $j$ まで移動するのに通る道路の長さの和の最小値です。

$K$ 個の都市に発電所を建設するときにかかるコストの最小値を求めてください。

入力

$NMK$
$A_1$ $A_2$ $\dots$ $A_N$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$⋮$
$X_M$ $Y_M$ $Z_M$

出力

$K$ 個の都市に発電所を建設するときにかかるコストの最小値を出力してください。最後に改行してください。

サンプル

3 2 2
3 5 8
1 2 9
2 3 2

15

4 3 3
10000 1 1 1
1 2 1
1 3 2 
1 4 1

8

10 10 1
1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000
1 2 1
2 3 10
3 4 100
4 5 1000
5 6 10000
6 7 100000
7 8 1000000
8 9 10000000
9 10 100000000
1 10 1000000000

1