Description

Let us consider the simplest travel problem: there are $N$ cities and $M$ bidirectional roads on this continent. The cities are numbered from $1$ to $N$. We start at city $1$ and need to reach city $N$. How can we arrive as fast as possible?

Is this not just the shortest path problem? We all know it can be solved using algorithms such as Dijkstra, Bellman-Ford, and Floyd-Warshall.

Now, we have $K$ SpellCards that can slow down time by $50\%$. That is, when traveling along an edge, we may choose to use one card, so the time to pass that road becomes half of the original. Note that:

1. On each road, at most one SpellCard can be used.
2. Using one SpellCard only takes effect on one road.
3. You do not have to use all SpellCards.

Given the above information, your task is to find the minimum time needed to travel from city $1$ to city $N$ when you may use at most $K$ time-slowing SpellCards.

Input Format

The first line contains three integers: $N$, $M$, $K$.

The next $M$ lines each contain three integers: $A_i$, $B_i$, $Time_i$, meaning there is a bidirectional road between $A_i$ and $B_i$. Without using a SpellCard, passing through it takes $Time_i$ time.

Output Format

Output one integer, the minimum time needed to travel from city $1$ to city $N$.

4 4 1 
1 2 4 
4 2 6 
1 3 8 
3 4 8 

7

Hint

Sample 1 Explanation

Without using any SpellCard, the shortest path is $1 \to 2 \to 4$, with total time $10$. Now we can use $1$ SpellCard, so we halve the time on the road $2 \to 4$, and the total time becomes $7$.

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1 \leq K \leq N \leq 50$, $M \leq 10^3$.
• $1 \leq A_i,B_i \leq N$, $2 \leq Time_i \leq 2 \times 10^3$.
• To ensure the answer is an integer, all $Time_i$ are even.
• The undirected graph in all data has no self-loops or multiple edges, and is connected.

Translated by ChatGPT 5