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 年