Hide

Problem G

Languages en is ja
/problems/bryr/file/statement/ja/img-0001.jpg
Photo courtesy of Wikimedia Commons

去年の話ですが、エヴァとステファンはウェストマン諸島に住んでいました。その頃、あなたはエバがステファンと一緒に最短時間で国中を探索するための最適な旅程を見つけるのを手伝ってくれました。今、エヴァはエギルスシュタイルをもう一度訪れたいと思っていますが、二人の旅の中で、ステファンは片側一車線の橋が嫌いだということがわかりました。エヴァはステファンの機嫌を損ねないように、またあなたの力を借りたいと思っています。

ウェストマン諸島からエギルスシュタイルまでの道で、できるだけ片側一車線の橋が少ない道をエバが見つけるのを手伝ってあげてください。

入力

最初の行には、$2$つの整数$2 \leq n \leq 10^5 $$n-1 \leq m \leq \min {(2\cdot 10^5, n(n-1)/2)}$が含まれています。それぞれ、場所の数と道路の数を表します。 次の$m$行には、それぞれ$3$つの数$1 \leq a, b \leq n$$c \in \{ 0, 1\} $ が含まれています。場所 $a$$b$ とを結ぶ道路があり、$c = 1$なら片側一車線の橋、$c = 0$なら片側二車線の橋が含まれることを表します。 ウェストマン諸島は場所 $1$ で、エギルシュタイルは場所 $n$ です。 アイスランドの交通システムにおいて、一方通行はありません。すなわち、どちらの場所からでももう一方の場所へ進むことができます。 また、各ペア$a, b$が入力に複数回含まれることはありません。

出力

ステファンとエヴァがルートの終点に着くまでに渡らなければならない片側一車線の橋の最小数を出力してください。

得点

Group

Points

Bounds

$1$

$20$

$1 \leq n \leq 100$, $n = m$, アイスランドの道路システムは、片側一車線の橋 ($c = 1$) による環状になっています。

$2$

$20$

$1 \leq n \leq 100$, すべての道路が片側一車線の橋 ($c = 1$) を含みます。

$3$

$20$

$1 \leq n \leq 100$

$4$

$20$

すべての道路が片側一車線の橋 ($c = 1$) を含みます。

$5$

$20$

追加の制約条件はありません。

サンプル入力 1 サンプル出力 1
3 3
3 1 1
1 2 1
2 3 1
1
サンプル入力 2 サンプル出力 2
6 6
5 6 1
5 4 1
2 1 1
2 3 1
4 3 1
1 4 1
3
サンプル入力 3 サンプル出力 3
10 13
7 3 0
7 10 1
8 2 0
10 2 1
4 6 0
4 1 0
9 5 1
6 9 0
7 6 1
3 10 0
4 5 0
5 7 1
4 8 0
1