Problem G
橋

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$が入力に複数回含まれることはありません。

出力

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

得点

3 3
3 1 1
1 2 1
2 3 1

1

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

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