Journey from Petersburg to Moscow

A network of toll roads was built in the European part of Russia for the World Programming Cup 2112. The network consists of $m$ bidirectional roads that connect $n$ cities. Each road connects two distinct cities, no two roads connect the same pair of cities, and you can travel from any city to any other city using only this network. To keep charging simple, no two roads cross outside of the cities.

Every road has its own positive cost. Normally a driver who uses these toll roads pays the sum of the costs of all roads on the trip. To attract more car travel between the two capitals, the operator Radishchev Inc introduced a special offer: on a journey from Saint Petersburg to Moscow you pay only for the $k$ most expensive roads of your path.

More precisely, suppose a path consists of $l$ roads. Let $c_1$ be the cost of the most expensive road on the path, $c_2$ the cost of the second most expensive one, and so on, so that $c_1 \ge c_2 \ge c_3 \ge \dots \ge c_l$. If $l \le k$, the path is too short for the offer and the driver pays the sum of all costs as usual, that is $\sum_{i=1}^{l} c_i$. If $l > k$, the driver pays only for the $k$ most expensive roads, that is $\sum_{i=1}^{k} c_i$.

As the chief analyst of Radishchev Inc, compute the cheapest possible journey from Saint Petersburg to Moscow.

The first line 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, and the largest number of roads one pays for on a single journey.

Each of the next $m$ lines describes one road with three integers $u_i$, $v_i$ and $w_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$, $1 \le w_i \le 10^9$): a bidirectional road between cities $u_i$ and $v_i$ that costs $w_i$ in either direction. At most one road connects each pair of cities, and the given roads let you reach every city from every other city.

Print one integer, the minimum possible cost of a journey from city $1$ (Saint Petersburg) to city $n$ (Moscow).