Farmer John は毎日、忠実に牛たちを見回ります。番号 $1,\ldots,M$ が付いた $M$ 本 $(1 \le M \le 50,000)$ の道のいくつかを通り、牧草地 $1$ から牧草地 $N$ まで行きます（テストデータの道の地図では、この移動は常に可能です）。Farmer John の農場にある $N$ 個 $(1 \le N \le 10,000)$ の牧草地には番号 $1,\ldots,N$ が付いており、現在は双方向の未舗装の道で結ばれています。各道 $i$ は牧草地 $P1_{i}$ と $P2_{i}$ $(1 \le P1_i \le N; 1 \le P2_i \le N)$ を結び、通るのに $T_{i}$ $(1 \le T_{i} \le 1,000,000)$ 単位の時間がかかります。

長い移動の時間を節約するため、農場の道の一部を改修したいと考えています。具体的には $K$ 本 $(1 \le K \le 20)$ の道を選んで幹線道路に変え、それぞれの通行時間を実質的に $0$ にします。牧草地 $1$ から $N$ への所要時間を最小にするため、どの道を改修すべきか FJ を助けてください。

入力

• 1 行目：空白で区切られた三つの整数 $N$、$M$、$K$。

• $2,\ldots,M+1$ 行目：$i+1$ 行目は、空白で区切られた三つの整数 $P1_{i}$、$P2_{i}$、$T_{i}$ で道 $i$ を記述します。

出力

• 1 行目：$K$ 本以下の辺を改修した後の最短経路の長さ。

入出力例

入力 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

出力 1

1

注記

$K$ は $1$ です。道 $3->4$ を改修し、所要時間を $100$ から $0$ にします。新しい最短経路は $1->3->4$ で、合計所要時間は $1$ になります。

問題作成：Percy Liang、2008 年