Pikachu has been kidnapped by Team Rocket's evil scheme! The three villains have left a blatant provocation for Ash. For the sake of Pikachu and justice, Ash and his friends have embarked on a mission to rescue Pikachu.

Team Rocket has a total of $N$ strongholds, with $M$ bidirectional roads connecting them. The strongholds are numbered from $1$ to $N$. Ash and his $K$ companions start 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$ people are at stronghold $0$.

Due to Team Rocket's heavy defenses, to destroy stronghold $K$, one must first destroy strongholds $1$ through $K-1$ in order. Furthermore, if stronghold $K-1$ has not been destroyed, the chain reaction of the defense system means that if any of Ash's group enters stronghold $K$, they will be detected, leading to severe consequences. Therefore, before stronghold $K-1$ is destroyed, no one can pass through stronghold $K$.

To simplify the problem, we ignore the combat phase; if any member of Ash's group passes through stronghold $K$, it is considered destroyed. Destroyed strongholds can still be traversed.

The $K$ people can act separately. As long as any one person passes through stronghold $K$ after stronghold $K-1$ has been destroyed, stronghold $K$ is considered destroyed. Obviously, once stronghold $N$ is destroyed, Pikachu is saved.

The roads in the wild are unsafe, so Ash and his group want to minimize the total length of the roads traversed by the $K$ people while destroying stronghold $N$ to rescue Pikachu.

Please help Ash design an optimal rescue plan!

Input

The first line contains three positive integers $N, M, K$, representing a total of $N+1$ strongholds (numbered $0$ to $N$) and $M$ undirected edges. Initially, all $K$ people are at stronghold $0$.

The next $M$ lines each contain three non-negative integers $A_i, B_i, L_i$, representing a road between stronghold $A_i$ and stronghold $B_i$ with length $L_i$.

Output

A single integer $S$, representing the minimum total road length required to rescue Pikachu.

Examples

Input 1

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

Output 1

3

Note 1

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

Constraints

• For $10\%$ of the data: $K = 1$ and $N = 3$.
• For $20\%$ of the data: $K \leq 3$ and $N \leq 20$.
• For $40\%$ of the data: $K \leq 3$ and $N \leq 100$.
• For another $20\%$ of the data: A path exists between any pair of strongholds, and for any $0 \leq X, Y, Z \leq N$, the inequality $L(X, Z) \leq L(X, Y) + L(Y, Z)$ holds.
• For $100\%$ of the data: $N \leq 150$, $M \leq 20,000$, $1 \leq K \leq 10$, $L_i \leq 10,000$. It is guaranteed that Ash and his group can always rescue Pikachu. As for why $K \leq 10$, you can assume that eventually, at Ash's call, Ash, Misty, Brock, Tracey, May, Max, Dawn, Iris, Cilan, and even Officer Black Cat (who was traveling in Japan) all went together to battle Team Rocket.