Description

This is a graph with $n$ nodes and $m$ undirected edges. Each edge has a length of $w$ units. zrz is at position $1$, and the exit is at position $n$.

However, zrz’s brain has a little bug: he does not want the shortest path; he wants the second-shortest path. The second-shortest path may share edges with the shortest path and may pass through some nodes and edges multiple times. Note that if there are multiple paths that are all shortest, none of them can be called the second-shortest path.

In addition, if the next node to enter has fewer than $k$ directly connected neighbors (excluding the start and the exit), then zrz will not dare to enter it.

Input Format

The first line contains three numbers: $n, m, k$.

The next $m$ lines each contain three numbers $u, v, w$, indicating there is an undirected edge of weight $w$ between $u$ and $v$.

Output Format

Output a single number: the length of the second-shortest path from $1$ to $n$. If it does not exist, output $-1$.

4 4 1
1 2 100
2 4 200
2 3 250
3 4 100

450

4 4 3
1 2 100
2 4 200
2 3 250
3 4 100

500

Hint

Constraints:

• For $50\%$ of the testdata: $n \leq 10$, $m \leq 10$.
• For $90\%$ of the testdata: $n \leq 1000$, $m \leq 20000$.
• For $100\%$ of the testdata: $1 \leq n \leq 5000$, $1 \leq m \leq 100000$, $1 \leq u, v \leq n$, $1 \leq w \leq 10000$.

Also, $k$ is relatively small.

In Sample $2$, the shortest path is $300$ (1-2-4). Because it is impossible to go from $2$ to $3$ ($3$ is connected to only $2$ nodes), it is allowed to go 1-2-1-2-4, and the second-shortest path is $500$.

Translated by ChatGPT 5