Problem K
Kanto To Johto

Red is a Pokemon trainer who has beaten the Kanto Pokemon League, and wants to get to Johto for new challenges. To get there, he needs to travel by train.

The region has $N$ train stations labelled from $1$ to $N$. Red starts at station $1$ and needs to get to station $N$ to enter Johto. There are $M$ bidirectional train lines, where the $i^{\text{th}}$ train line connects stations $X_i$ and $Y_i$, and multiple train lines may connect the same pair of cities. It is possible to get from city $1$ to city $N$ with the train lines, but it may not be possible to get from city $1$ to some other cities with the train lines.

To use the $i^{\text{th}}$ train line, Red needs to pay $C_i$ dollars for a lifetime pass, after which he may use the train line as many times as he wants. He can only purchase the pass for the $i^{\text{th}}$ train line when he is at station $X_i$ or $Y_i$, and he can only purchase it once.

The payment system is online, where Red only needs to make a delayed bulk payment for the passes he bought when he enters Johto (due to immigration policies). Note that when he reaches station $N$, he does not need to pay yet, and can continue taking trains. He only pays when he exits station $N$ and reaches the immigration counter.

Due to a bug in the system, he will only need to pay for the passes with the $K$ smallest costs (or all of them if he bought fewer than $K$ passes) when he reaches Johto.

Help Red determine the minimum amount of money (in dollars) he needs to spend to get from Kanto to Johto.

Input

The first line of the input contains 3 integers $N, M, K$ ($2 \leq N \leq 10^5$, $1 \leq K \leq M \leq 2 \cdot 10^5$).

The next $M$ lines of the input each contain 3 integers $X_i, Y_i, C_i$ ($1 \leq X_i, Y_i \leq N$, $X_i \neq Y_i$, $1 \leq C_i \leq 10^9$).

It is guaranteed that Red can get from station $1$ to station $N$ using the train lines.

Output

Output a single integer, the minimum amount of money (in dollars) Red needs to spend to get from station $1$ to station $N$.

Sample Explanation

In the first sample, note that Red cannot buy the pass for the train line connecting stations $3$ and $6$, as there is no way to reach those cities by train.

To get to city $N$, Red may buy the pass to travel between stations $1$ and $2$, travel to station $2$, buy the pass to travel between stations $2$ and $7$, travel to station $7$, buy the pass to travel between stations $7$ and $5$, travel to station $5$, buy the pass to travel between stations $5$ and $4$, travel back to station $7$ (note that he does not have to travel to station $4$ after buying the pass), then go to immigration.

The passes he buys cost $3, 3, 2, 2$ in that order, and he pays for the $K = 2$ cheapest, for a cost of $2 + 2 = 4$. It can be shown this is the minimum possible.

In the second sample, Red may travel $1 \rightarrow 2 \rightarrow 6 \rightarrow 4 \rightarrow 7$, buying the passes between consecutive cities in the route, and pay $4 + 3 + 2 + 3 = 12$ as he only buys $4$ passes but $K = 5$. It can be shown this is the minimum possible.

In the third sample, Red may buy all the passes, and he only pays for the $K = 2$ passes between stations $1$ and $2$ which cost $1$ each, for a total cost of $1 + 1 = 2$.

7 5 2
1 2 3
2 7 3
5 4 2
7 5 2
3 6 1

4

7 10 5
1 2 4
2 6 3
6 4 2
3 5 7
4 7 3
3 7 1
2 4 10
1 3 12
5 7 4
4 5 4

12

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

2