E問題 - あみだくじ

実行時間制限: 2 sec / メモリ制限: 1024 MB

問題文

真の鶴の剣を持った勇者一行はダンジョンに挑みます。 ダンジョンには道が\(N\)本存在しており、道と道を繋ぐ橋が\(M\)本あります。 また、道\(_i(1 \leq i \leq M)\)の始点から\(K\)だけ進んだ位置を、道\(_i\)の位置\(K\)と表記します。

このダンジョンには呪いがかかっており道に橋が架かっているならば必ず渡らなければいけません。 また、橋を通るにはそれぞれコスト\(C_i(1 \leq i \leq M)\)がかかります。

ダンジョンの入口は道\(_1\)の初めにあり、出口は道\(_G\)の終わりに存在しています。 ダンジョンをクリアするには入口から出口に行く必要があります。

橋\(i(1 \leq i \leq M)\)は道\(_{A_i}\)の位置\(X_i(X_i \neq X_j(i \neq j))\)と道\(_{B_i}\)の位置\(Y_i(Y_i \neq Y_j(i \neq j))\)を結ぶように設置されています。 また橋が重なることはありません。

橋が適切に配置されたとき、勇者一行がダンジョンをクリアできる最小のコストを出力してください。またクリアできない場合は、Noを出力してください。

制約

• \(2 \leq G \leq N \leq 2 \times 10^5\)
• \(1 \leq M \leq 2 \times 10^5\)
• \(1 \leq C_i \leq 10^9\)
• \(1 \leq A_i \leq B_i \leq N\)
• \(A_i=1\) かつ \(B_i=G\) であるような\(i(1 \leq i \leq M)\) は多くとも\(1\)つ

入力

入力は以下の形式で与えられます。

N M G
A_1 B_1 C_1
...
A_M B_M C_M

出力

標準出力に一行で出力せよ。

入出力例

入力例1

2 1 2
1 2 3

出力例1

3

• 道\(1\)と道\(2\)つなぐ橋\(1\)を設置すれば良いです。

入力例2

6 5 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

出力例2

5000000000

• コストは32bit整数型に収まらない場合があります。
• 橋\(1\)、橋\(2\)、...の順に橋を設置することでクリアすることが出来ます。

入力例3

3 1 2
1 3 2

出力例3

No

• どのように橋を設置してもクリアすることはできません。
• クリアできないときはNoを出力することに注意してください。