题目描述

To conduct The World Programming Cup $2112$ a network of wonderful toll roads was build in European part of Russia. This network consists of $m$ bidirectional roads that connect $n$ cities. Each road connects exactly two distinct cities, no two roads connect the same pair of cities, and it is possible to travel from any city to any other city using only this road network. Moreover, to ease the process of charging, no two roads intersect outside of the cities.

Each road is assigned some individual positive cost. Normally, if a driver makes a trip using some of these toll roads, at the end of his journey he would be charged the total cost equal to the sum of individual costs of all roads he has used. To increase the popularity of car travels between two capitals, the operator company Radishchev Inc introduced a special offer: make a journey from Saint Petersburg to Moscow and pay for only $k$ most expensive roads along your path.

Formally, let some path consists of $l$ roads. Denote as $c_{1}$ the cost of the most expensive road along this path, as $c_{2}$ the second most expensive and so on. Thus, we have a sequence $c_{1} \ge c_{2} \ge c_{3} \ge$ . . . $\ge c_{l}$ of individual costs of all roads along the chosen path. If $l \le k$ , then the path is too short and the driver pays the sum of all individual costs as usual, i.e . $Σ^{l}_{i=1}c_{i}.$ If $l > k$ , then the driver only pays for $k$ most expensive roads, that is $Σ^{k}_{i=1}c_{i}.$

As the chief analyst of Radishchev Inc you were assigned a task to compute the cheapest possible journey from Saint Petersburg to Moscow.

输入格式

The first line of the input contains three integers $n , m$ and $k (2 \le n \le 3000 , 1 \le m \le 3000 , 1 \le k < n)$ -- the number of cities, the number of roads in the road network, and the maximum number of roads that one should pay for in a single journey.

Next $m$ lines contain description of roads. Each road description contains three integers $u_{i}, v_{i},$ and $w_{i} (1 \le u_{i}, v_{i} \le n , u_{i} ≠ v_{i}, 1 \le w_{i} \le 10^{9})$ -- the i-th bidirectional road that connects cities $u_{i}$ and $v_{i}$ with the cost of $w_{i}$ for any direction. It is guaranteed that there is at most one road between each pair of cities and it is possible to get from any city to any other city using only these roads.

输出格式

Print one integer equal to the minimum possible cost of travel from the city number $1$ (Saint Petersburg) to the city number $n (Moscow).$

题目大意

有 $n$ 座城市 $m$ 条道路，每条道路连接两座城市，每条道路都需要过路费。

$\mathsf{\color{black}{K}\color{red}{arry5307}}$ 想从城市 $1$ 出发前往城市 $n$。根据相关法律法规，对于一条经过 $c$ 条边的路径，$\mathsf{\color{black}{K}\color{red}{arry5307}}$ 只需要支付路径上前 $k$ 大的过路费（当 $c<k$ 时需要支付路径上全部的过路费）。

现在 $\mathsf{\color{black}{K}\color{red}{arry5307}}$ 想要求出从 $1$ 到达 $n$ 的最小花费。因为 $\mathsf{\color{black}{K}\color{red}{arry5307}}$ 忙着写神仙题，所以这个任务交给了你。

$2\leq n\leq 3000,1\leq m\leq 3000,1\leq k<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

提示

Time limit: 3 s, Memory limit: 512 MB.