Background

“I want to become a magical girl.”

“Then, in exchange for your soul, what do you wish to obtain?”

“I want to seal everything about magic and miracles into cards...”

In the world after this wish comes true, people enjoy the convenience brought by magic cards (SpellCard, also known as “符卡”).

Now, you can use magic without making a contract! Why not give it a try?

For example, if we search the Encyclopedia of Spells with the keyword “freeze”, we will get many interesting results.

For instance, the well-known Cirno surely has a corresponding SpellCard for her freezing magic. Even more surprising, there is actually magic that can freeze time. Compared with these, Cirno’s frozen frogs are nothing.

This shows that in the previous world, many magical girls once made wishes to control time, such as Akemi Homura, Sakuya Izayoi, ...

Of course, in this problem we are not studying history, but the application of magic.

Problem 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