Farmer John は農場に電話線を設置したいと考えています。残念ながら電話会社が協力的でないため、農場を電話網につなぐために必要なケーブルの一部を自費で用意しなければなりません。
Farmer John の土地には $N$ 本（$(1 \le N \le 1,000)$）のぽつんとした電話用電柱が点在し、便宜上 $1..N$ と番号が付いています。現在、電柱同士をつなぐケーブルはありません。合計 $P$ 組（$(1 \le P \le 10,000)$）の電柱の対はケーブルで接続できますが、ほかの対は離れすぎています。
$i$ 番目のケーブルは異なる電柱 $A_i$ と $B_i$ を結び、使用すると長さは $L_i$ 単位です。$(1 \le L_i \le 1,000,000)$ です。入力で同じ対 {$A_i,B_i$} が 2 回以上与えられることはありません。電柱 $1$ はすでに電話網につながり、電柱 $N$ は農場にあります。電柱 $1$ と $N$ をケーブルの経路でつなぐ必要があり、ほかの電柱は使っても使わなくても構いません。
実は電話会社は Farmer John に $K$ 本（$(0 \le K < N)$）のケーブルを無料で提供してくれます。それ以外については、必要な残りのケーブルの最長のものの長さに等しい料金を払います（各電柱の対を別々のケーブルで結びます）。追加のケーブルが必要なければ料金は $0$ です。
Farmer John が支払わなければならない最小金額を求めてください。
入力
入力は標準入力から読み込んでください。
1 行目：空白区切りの 3 つの整数 $N$、$P$、$K$。
$2..P+1$ 行目：$i+1$ 行目には空白区切りの 3 つの整数 $A_i$、$B_i$、$L_i$ が与えられます。
出力
出力は標準出力に書き込んでください。
- 1 行目：Farmer John が払える最小金額を表す整数を 1 つ。農場を電話会社につなげない場合は $-1$ を出力してください。
入出力例
入力 1
5 7 1 1 2 5 3 1 4 2 4 8 3 2 3 5 2 9 3 4 7 4 5 6
出力 1
4
注記
電柱は 5 本あります。電柱 $1$ は電柱 $4$ や $5$ に直接つなげません。電柱 $5$ は電柱 $1$ や $3$ に直接つなげません。ほかのすべての対は接続できます。電話会社はケーブルを 1 本無料で提供します。
電柱 $1$ を $3$ に、$3$ を $2$ に、$2$ を $5$ につなぐと、Farmer John は長さ $4$、$3$、$9$ のケーブルを必要とします。電話会社が長さ $9$ のケーブルを提供するので、残りの必要なケーブルの最長の長さは $4$ です。
問題作成：Paul Christiano、2007