Problem G
Brýr

Mynd fengin af Wikimedia Commons

Eins og allir vita frá því í fyrra þá búa Eva og Stefán í Vestmannaeyjum. Þá hjálpaðir þú Evu að finna bestu ferðaáætlunina til að skoða allt landið með honum Stefáni á sem stystum tíma. Núna langar Evu aftur að heimsækja Egilsstaði en á ferð sinni í kringum landið þá fundu þau út að Stefán HATAR einbreiðar brýr. Hún Eva leitar því aftur til þín til að hjálpa sér að halda Stefáni í góðu skapi.

Getur þú hjálpað Evu að finna leiðina frá Vestmannaeyjum til Egilsstaða sem inniheldur sem fæstar einbreiðar brýr?

Inntak

Í fyrstu línu koma tvær heiltölur, $2 \leq n \leq 10^5$, fjöldi staða, $n-1 \leq m \leq \min {(2\cdot 10^5, n(n-1)/2)}$ fjöldi vega. Næst koma $m$ línur hver með $3$ tölum $1 \leq a, b \leq n$ og $c \in \{ 0, 1\} $ sem þýðir að það er vegur sem liggur á milli staðar $a$ og staðar $b$ og inniheldur einbreiða brú ef $c = 1$, en tvíbreiða brú ef $c=0$. Vestmannaeyjar munu alltaf vera númer $1$ og Egilsstaðir munu alltaf vera númer $n$. Þú mátt gera ráð fyrir að vegakerfi Íslands sé samhangandi: það er hægt að komast á hvern einasta stað frá hverjum einasta stað. Þú mátt einnig gera ráð fyrir að hvert par $a, b$ kemur mesta lagi einu sinni fyrir í inntakinu.

Úttak

Ein lína með minnsta fjölda einbreiðra brúa sem Stefán og Eva þurfa að fara yfir til að komast á leiðarenda.

Stigagjöf

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