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$} 給出超過一次。電話桿 $1$ 已經接入電話系統，電話桿 $N$ 位於農場。需要用一條電纜路徑連接電話桿 $1$ 與 $N$；其他電話桿可以使用，也可以不使用。

事實上，電話公司願意免費提供 $K$ 根電纜給 Farmer John，$(0 \le K < N)$。除此之外，他必須支付的費用等於所需其餘電纜中最長一根的長度（每對電話桿以一根獨立電纜相連）；若不需要額外電纜，則費用為 $0$。

求出 Farmer John 必須支付的最少金額。

輸入格式

從標準輸入讀取輸入。

• 第 1 行：三個以空格分隔的整數：$N$、$P$ 與 $K$。

• 第 $2..P+1$ 行：第 $i+1$ 行包含三個以空格分隔的整數：$A_i$、$B_i$ 與 $L_i$。

輸出格式

將輸出寫入標準輸出。

• 第 1 行：一個整數，代表 Farmer John 可以支付的最少金額。若無法將農場連接到電話公司，輸出 $-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$ 連到 $3$，$3$ 連到 $2$，$2$ 連到 $5$，Farmer John 便需要長度為 $4$、$3$ 與 $9$ 的電纜。電話公司會提供長度為 $9$ 的電纜，所以剩餘所需電纜中最長的長度為 $4$。

題目作者：Paul Christiano，2007