题目描述

农夫约翰每天都会认真检查他的奶牛。他会穿越一些编号为 $1$ 到 $M$ 的小径，从牧场 $1$ 一直走到牧场 $N$（对于测试数据给出的路径图，这段旅程总是可能的）。约翰的农场上有 $N$ 个牧场，它们通过双向泥土小径连接在一起。每条小径 $i$ 连接牧场 $P1_i$ 和 $P2_i$，需要 $T_i$ 单位时间来穿越。

他想要改造农场上的一些小径，以节省长途旅行的时间。具体来说，他将选择 $K$ 条小径将其改造成高速公路，这将有效地将小径的穿越时间减少到 $0$。帮助 FJ 决定改造哪些小径以最小化从牧场 $1$ 到 $N$ 的最终时间。

输入格式

第一行包含三个用空格分隔的整数 $N, M, K$。

第 $2$ 行到第 $M+1$ 行每行描述一条小径，包含三个用空格分隔的整数 $P1_i, P2_i, T_i$，表示一条连接 $P1_i$ 和 $P2_i$ 的双向小径，穿越时间为 $T_i$。

输出格式

一个整数，表示改造不超过 $K$ 条边后的最短路径长度。

样例

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

1

数据范围

• $1 \le N \le 10,000$
• $1 \le M \le 50,000$
• $1 \le K \le 20$
• $1 \le P1_i, P2_i \le N$
• $1 \le T_i \le 10^6$