Problem Description

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$.

Input Format

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 Format

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

6 6 6
1 2 5
2 4 5
1 3 2
3 4 100
4 5 10
5 6 20

5

Hint

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