Rescue Pikachu

Problem Source

ZJOI 2011

Problem Description

Pikachu has been kidnapped by Team Rocket using an evil trick, and they even left a naked provocation for Ash! For Pikachu's sake, and for justice, Ash and his friends set out on a journey to rescue Pikachu without hesitation.

Team Rocket has $N$ strongholds, with $M$ bidirectional roads between them. The strongholds are numbered from $1$ to $N$. Ash and his group of $K$ companions set out from Pallet Town to rescue Pikachu, who is trapped in stronghold $N$. For convenience, we treat Pallet Town as stronghold $0$, and initially all $K$ companions are at stronghold $0$.

Because of Team Rocket's heavy defences, to destroy stronghold $x$ you must first destroy strongholds $1$ through $x-1$ in order; moreover, if stronghold $x-1$ has not been destroyed, due to the chain of defence, anyone from Ash's group who enters stronghold $x$ will be discovered, with serious consequences. Therefore, no one is allowed to pass through stronghold $x$ before stronghold $x-1$ is destroyed.

To simplify the problem, we ignore the fighting phase: anyone from Ash's group passing through stronghold $x$ is considered to have destroyed stronghold $x$. A destroyed stronghold can still be passed through.

The $K$ companions may split up and act separately; as long as any one of them passes through stronghold $x$ after stronghold $x-1$ is destroyed, stronghold $x$ is destroyed. Obviously, once stronghold $N$ is destroyed, Pikachu is saved.

The roads in the wild are unsafe, so Ash's group hopes that, while rescuing Pikachu by destroying stronghold $N$, the total length of roads travelled by the $K$ companions is minimized.

Please help Ash design the best rescue plan!

Input Format

The first line contains three positive integers $N\ (1 \le N \le 150), M\ (1 \le M \le 2 \times 10^4), K\ (1 \le K \le 10)$. There are $N+1$ strongholds in total, numbered from $0$ to $N$, and $M$ undirected edges. Initially all $K$ companions of Ash's group are at stronghold $0$.

The next $M$ lines each contain three non-negative integers; the $i$-th line has $A_i, B_i, L_i\ (0 \le L_i \le 10^4)$, meaning there is a road of length $L_i$ from stronghold $A_i$ to stronghold $B_i$. It is guaranteed that Ash's group can certainly rescue Pikachu.

Output Format

Contains only one integer $S$: the minimum total length of roads that must be travelled to rescue Pikachu.

Sample Input

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

Sample Output

3

Hint

Ash and Misty go together to rescue Pikachu. In the optimal plan, Ash first goes from Pallet Town to stronghold 1, then to stronghold 2. After Ash destroys stronghold 2, Misty sets out from Pallet Town straight to stronghold 3 and rescues Pikachu.

As for why $K \le 10$, you may think of it as: inspired by Ash, Ash, Misty, Brock, Tracey, May, Max, Dawn, Iris, Cilan, and the Police Inspector Black Cat who is travelling in Japan, all go together to battle Team Rocket.