给定一张包含 n 个点、m 条无向边的图，点的编号为 1 ∼ 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
【样例说明】
由于 X =6，而出发点也是 6，因此一开始就已经获得了 3 次特殊机会。
一种 最 优 走 法 为： 6 → 5 → 4 → 3 → 1，对 应 边 的 原 代 价 分 别 为20, 10, 100, 2。
在其中 3 条边上使用特殊机会，例如对代价为 20, 10, 100 的三条边使用，则这三次经过的代价都变为 1，最后一条边仍支付原代价 2。
因此总代价为 1+ 1 + 1 + 2 = 5
【评测用例规模与约定】
对于 30% 的评测用例，n, m ≤ 500。
另有额外 30% 的评测用例，所有边的代价 w 相同。
对于所有的评测用例，1 ≤ n ≤ 2 × 105，1 ≤ m ≤ 2 × 105，1 ≤ w ≤ 109，
1 ≤ X, u, v ≤ n。
保证图中不含自环，但可能存在重边。