Description

Pikachu has been taken away by Team Rocket using an evil scheme. Those three bad guys also left Ash with an open provocation. For Pikachu, and for justice, Ash and his friends set off without hesitation on the road to rescue Pikachu.

Team Rocket has a total of $N$ bases, and there are $M$ bidirectional roads between the bases. The bases are numbered from $1$ to $N$. Ash’s team has $K$ people. They start from Pallet Town and plan to rescue Pikachu trapped in base $N$. For convenience, we treat Pallet Town as base $0$. At the beginning, all $K$ people are at node $0$.

Due to Team Rocket’s heavy defenses, for any $2\le X\le N$, to destroy base $X$, one must first destroy bases $1$ to $X-1$ in order. Moreover, if base $X-1$ has not been destroyed, then because of chained defenses, once any member of Ash’s team enters base $X$, they will be discovered and serious consequences will occur. Therefore, before base $X-1$ is destroyed, no one can pass through base $X$.

To simplify the problem, we ignore fighting. If any member of Ash’s team passes through base $K$, then base $K$ is considered destroyed. A destroyed base can still be passed through.

The $K$ people may act separately. As long as after base $K-1$ is destroyed, any one person passes through base $K$, then base $K$ is destroyed. Obviously, once base $N$ is destroyed, Pikachu is rescued.

The roads in the wild are unsafe, so while destroying base $N$ to rescue Pikachu, Ash’s team wants the total length of roads traveled by all $K$ people to be as small as possible.

Please help Ash design the best rescue plan.

Input Format

The first line contains three positive integers $N,M,K$. This means there are $N+1$ nodes numbered from $0$ to $N$, and $M$ undirected edges. At the beginning, Ash’s team has $K$ people, all located at node $0$.

The next $M$ lines each contain three non-negative integers. On the $i$-th line, the integers are $A_i$, $B_i$, $L_i$, meaning there is a road of length $L_i$ between base $A_i$ and base $B_i$.

Output Format

Output only one integer $S$, the minimum total road length required to rescue Pikachu.

3 4 2
0 1 1
1 2 1
2 3 100
0 3 1

3

Hint

[Sample Explanation]

Ash and Misty go to rescue Pikachu together. In the optimal plan, Ash first goes from Pallet Town to node $1$, then goes to base $2$. After Ash successfully destroys base $2$, Misty sets off from Pallet Town and goes directly to base $3$, rescuing Pikachu.

For $100\%$ of the testdata, it holds that $N\le 150, M \le 20 000, 1 \le K \le 10, L_i \le 10 000$. It is guaranteed that Ash’s team can rescue Pikachu.

As for why $K \le 10$, you may assume that in the end, under Ash’s call, Ash, Misty, Brock, Tracey, May, Max, Dawn, Iris, Cilan, and also Officer Black Cat who is traveling in Japan, all go together to fight Team Rocket.

Translated by ChatGPT 5