Problem B
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\le n\le {10}^5$, fjöldi staða, $n-1\le m\le min(2\cdot {10}^5,n(n-1)/2)$ fjöldi vega. Næst koma $m$ línur hver með $3$ tölum $1\le a,b\le 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