为了举办 2112 年世界编程杯，俄罗斯欧洲部分修建了一个宏伟的收费公路网络。该网络由 $m$ 条连接 $n$ 个城市的双向道路组成。每条道路连接两个不同的城市，任意两个城市之间最多只有一条道路，且保证仅通过这些道路即可从任意城市到达其他任何城市。此外，为了简化收费流程，没有任何两条道路在城市之外相交。

每条道路都有一个正整数费用。通常情况下，如果司机使用其中的一些收费公路，在旅程结束时，他需要支付的费用等于他所经过的所有道路的费用之和。为了提高两座首都之间汽车旅行的受欢迎程度，运营商 Radishchev Inc 推出了一项特别优惠：从圣彼得堡前往莫斯科的旅程中，只需支付路径上 $k$ 条最昂贵道路的费用。

形式化地，设某条路径包含 $l$ 条道路。记 $c_1$ 为该路径上最昂贵道路的费用，$c_2$ 为第二昂贵的，以此类推。这样，我们得到路径上所有道路费用的序列 $c_1 \ge c_2 \ge c_3 \ge \dots \ge c_l$。如果 $l \le k$，则路径较短，司机照常支付所有道路的费用之和，即 $\sum_{i=1}^l c_i$。如果 $l > k$，则司机只需支付 $k$ 条最昂贵道路的费用，即 $\sum_{i=1}^k c_i$。

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

输入格式

第一行包含三个整数 $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$。保证任意两个城市之间最多只有一条道路，且保证图是连通的。

输出格式

输出一个整数，表示从城市 1（圣彼得堡）到城市 $n$（莫斯科）的最小旅程费用。

样例

样例输入 1

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

样例输出 1

14

样例输入 2

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

样例输出 2

2