P16273 [Lanqiao Cup 2026 NOI Qualifier Java B Group] Return Trip

Given a graph with $n$ nodes and $m$ undirected edges, the nodes are numbered $1 \sim n$. Each edge connects two different nodes, and multiple edges may exist. Each undirected edge is described by three integers $u, v, w$, meaning there is an undirected edge between node $u$ and node $v$ with cost $w$. You need to start from node $n$ and reach node $1$. There is a special node $X$ in the graph. When you arrive at node $X$ for the first time, you can obtain **3** special chances. If $X = n$, it means you already have these **3** special chances at the start. During the subsequent trip, each time you traverse an edge, you may choose whether to use one special chance: - If you do not use it, the cost to traverse this edge is its original cost $w$. - If you use it, the cost to traverse this edge becomes $1$. You may use fewer or none of the special chances, but in total you can use at most **3** times, and each use only applies to the single edge you are traversing at that moment. Now, compute the minimum total cost from node $n$ to node $1$. If node $1$ cannot be reached, output $-1$.

The first line contains three integers $n, m, X$, representing the number of nodes, the number of edges, and the position of the special node. The next $m$ lines each contain three integers $u, v, w$, representing an undirected edge connecting node $u$ and node $v$ with cost $w$.

Output one integer, the minimum total cost from node $n$ to node $1$. If it is impossible to reach, output $-1$.

### Sample Explanation Since $X = 6$ and the starting node is also $6$, you already have **3** special chances at the beginning. One optimal route is: $6 \to 5 \to 4 \to 3 \to 1$, and the original edge costs are $20, 10, 100, 2$, respectively. Use special chances on **3** of these edges, for example on the edges with costs $20, 10, 100$. Then the costs of these three traversals all become $1$, and the last edge still costs $2$. So the total cost is $1 + 1 + 1 + 2 = 5$. ### Constraints For $30\%$ of the testdata, $n, m \leq 500$. For another $30\%$ of the testdata, all edge costs $w$ are the same. For all testdata, $1 \leq n \leq 2 \times 10^5$, $1 \leq m \leq 2 \times 10^5$, $1 \leq w \leq 10^9$, $1 \leq X, u, v \leq n$. It is guaranteed that the graph has no self-loops, but multiple edges may exist. Translated by ChatGPT 5