Description

为了举办世界编程杯 $2112$，在俄罗斯的欧洲部分建造了一张奇妙的收费公路网络。这个网络由 $m$ 条双向道路组成，连接了 $n$ 座城市。每条道路连接恰好两座不同的城市，没有两条道路连接相同的城市对，并且可以仅使用这张公路网络从任何城市到达其他城市。此外，为了简化收费过程，没有两条道路在城市外相交。

每条道路都有一个单独的正费用。通常情况下，如果司机使用这些收费公路进行旅行，在旅程结束时，他将支付等于所使用的所有道路的单个费用之和的总费用。为了增加两座首都之间汽车旅行的受欢迎程度，运营公司 Radishchev Inc 推出了一项特别优惠：从圣彼得堡到莫斯科的旅程只需支付路径上 $k$ 条最贵道路的费用。

正式地，假设某条路径由 $l$ 条道路组成。记 $c_{1}$ 为该路径上最贵的道路的费用，$c_{2}$ 为第二贵的，以此类推。因此，我们有一个序列 $c_{1} \ge c_{2} \ge c_{3} \ge \ldots \ge c_{l}$，表示所选路径上所有道路的单个费用。如果 $l \le k$，则路径太短，司机按通常方式支付所有单个费用之和，即 $\Sigma^{l}_{i=1}c_{i}$。如果 $l > k$，则司机只需支付 $k$ 条最贵道路的费用，即 $\Sigma^{k}_{i=1}c_{i}$。

作为 Radishchev Inc 的首席分析师，你的任务是计算从圣彼得堡到莫斯科的最低可能旅程费用。

Input Format

输入的第一行包含三个整数 $n, m$ 和 $k$ $(2 \le n \le 3000, 1 \le m \le 3000, 1 \le k < n)$——城市的数量、道路网络中的道路数量，以及单次旅程中需要支付的最多道路数量。

接下来的 $m$ 行包含道路的描述。每条道路的描述包含三个整数 $u_{i}, v_{i},$ 和 $w_{i}$ $(1 \le u_{i}, v_{i} \le n, u_{i} \neq v_{i}, 1 \le w_{i} \le 10^{9})$——第 $i$ 条双向道路连接城市 $u_{i}$ 和 $v_{i}$，费用为 $w_{i}$，无论方向如何。保证每对城市之间最多只有一条道路，并且仅使用这些道路可以从任何城市到达其他城市。

Output Format

输出一个整数，表示从城市编号 $1$（圣彼得堡）到城市编号 $n$（莫斯科）的最低可能旅行费用。

6 7 2
1 2 6
2 3 1
2 4 3
2 5 5
3 6 10
4 6 9
5 6 8

14

5 5 3
2 1 1
3 2 1
4 3 1
4 5 1
1 5 2

2

Hint

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。