题目描述

给定一张包含 $n$ 个点、$m$ 条无向边的图，点的编号为 $1 \sim n$。每条边连接两个不同的点，且可能存在重边。每条无向边由三个整数 $u, v, w$ 描述，表示点 $u$ 与点 $v$ 之间有一条无向边，其代价为 $w$。

你需要从点 $n$ 出发，到达点 $1$。

图中有一个特殊点 $X$。当第一次到达点 $X$ 时，可以获得 3 次特殊机会。若 $X = n$，则表示出发时就已经获得这 3 次特殊机会。

在之后的行进过程中，每次经过一条边时，都可以选择是否使用一次特殊机会：

• 如果不使用，则经过这条边的代价为该边原本的代价 $w$；
• 如果使用，则这一次经过该边的代价变为 $1$。

特殊机会可以少用或不用，但总共最多只能使用 3 次，每次只能作用于当前经过的一条边。

现在，请你计算从点 $n$ 到点 $1$ 的最小总代价。若无法到达，则输出 $-1$。

输入格式

第一行包含三个整数 $n, m, X$，分别表示点数、边数和特殊点的位置。

接下来 $m$ 行，每行包含三个整数 $u, v, w$，表示一条连接点 $u$ 与点 $v$ 的无向边，其代价为 $w$。

输出格式

输出一个整数，表示从点 $n$ 到点 $1$ 的最小总代价。若无法到达，则输出 $-1$。

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

5

解释 #1

由于 $X = 6$，而出发点也是 $6$，因此一开始就已经获得了 3 次特殊机会。

一种最优走法为：$6 \to 5 \to 4 \to 3 \to 1$，对应边的原代价分别为 $20, 10, 100, 2$。

在其中 3 条边上使用特殊机会，例如对代价为 $20, 10, 100$ 的三条边使用，则这三次经过的代价都变为 $1$，最后一条边仍支付原代价 $2$。

因此总代价为 $1 + 1 + 1 + 2 = 5$

数据范围

• 对于 $30\%$ 的评测用例，$n, m \leq 500$。
• 另有额外 $30\%$ 的评测用例，所有边的代价 $w$ 相同。
• 对于所有的评测用例，$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$。

保证图中不含自环，但可能存在重边。