Start

2019-03-23 10:00 UTC

Alfa 2019

End

2019-03-23 16:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -239 days 6:21:39

Time elapsed

6:00:00

Time remaining

0:00:00

Problem J
Brýr

/problems/iceland.bryr/file/statement/is/img-0001.jpg
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

Hópur

Stig

Takmarkanir

1

20

$1 \leq n \leq 100$, $n = m$, Vegakerfi Íslands myndar eina hringrás af einbreiðum brúm ($c = 1$)

2

20

$1 \leq n \leq 100$, allir vegir innihalda einbreiða brú ($c = 1$)

3

20

$1 \leq n \leq 100$

4

20

Allir vegir innihalda einbreiða brú ($c = 1$)

5

20

Engar frekari takmarkanir

Sample Input 1 Sample Output 1
3 3
3 1 1
1 2 1
2 3 1
1
Sample Input 2 Sample Output 2
6 6
5 6 1
5 4 1
2 1 1
2 3 1
4 3 1
1 4 1
3
Sample Input 3 Sample Output 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