P2829 The Great Escape

zrz walked into a peculiar maze. He found himself lost and wanted to get out. After barely finishing counting all the roads, he was so tired that he almost fainted, so he asked you for help.

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.

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 a single number: the length of the second-shortest path from $1$ to $n$. If it does not exist, output $-1$.

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