Description

WJJ likes traveling. This time, she plans to visit a valley that is said to have many beautiful waterfalls.

WJJ has obtained a map in advance. The map marks $N$ habitats of small animals, that is, small villages. Village $1$ is where WJJ currently lives, and village $N$ is where WJJ plans to go.

There are $M$ bidirectional roads connecting these villages. The $i$-th bidirectional road directly connects two villages $A_i$ and $B_i$, with length $C_i$. Some roads are tunnels, and some are plank bridges. Roads that seem to cross outside villages on the map do not actually intersect. In other words, if we view the villages and bidirectional roads as a graph in graph theory, we do not guarantee that it is a planar graph, nor do we guarantee that there are no multiple edges. However, one thing is guaranteed: WJJ has carefully verified that she can definitely travel from the village she lives in to the valley she wants to go to.

In WJJ’s magical world, each small animal can use a cactus to cast magic. One of the spells is to swap the lengths of any two bidirectional roads in the world, while keeping the lengths of all other roads unchanged. With WJJ’s current magic level, she can use this road-length swapping spell at most $K$ times. Unfortunately, since cacti have many thorns, WJJ does not plan to carry one during her trip, so she will finish all planned road swaps at home before setting out.

Assume that during WJJ’s trip, no other animals will swap roads to ruin her planned route. To reach the destination as quickly as possible, WJJ wants the total distance she needs to travel to be as short as possible. That is, after using the spell at most $K$ times, what is the shortest distance from village $1$ to village $N$?

Input Format

The first line contains $3$ integers $N, M, K$ separated by spaces.

The next $M$ lines each contain $3$ integers separated by spaces, representing $A_i, B_i, C_i$.

Output Format

Output one integer, the shortest distance between village $1$ and village $N$ after using the spell at most $K$ times.

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

3

Hint

Sample Explanation

One feasible plan is to swap the lengths of edge $1$ and edge $4$, and then swap the lengths of edge $2$ and edge $5$. After swapping, the shortest path is $1\rightarrow 2\rightarrow 5$, with length $3$. It can be proven that there is no better plan.

Constraints

For $100\%$ of the testdata, $1\leq N\leq 50$, $1\leq M\leq 150$, $1\leq K\leq 20$, $1\leq A_i,B_i\leq N$, $A_i\neq B_i$, $1\leq C_i\leq 1000$.

Translated by ChatGPT 5