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$。請幫助 FJ 決定改造哪些道路，使從牧場 $1$ 到 $N$ 的時間最短。

輸入格式

• 第 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 年