Hide

Problem J
Brýr

Languages en is ja
/problems/bryr/file/statement/en/img-0001.jpg
Image from Wikimedia Commons

As everyone knows from last year, Eva and Stefán live in Vestmannaeyjar. You helped Eva find the best travel plan to tour the entire country with Stefán in the least amount of time. Now Eva wants to visit Egilsstaðir, but travelling around the country lead to them finding out that Stefán HATES single-lane bridges. Thus Eva looks to you once more to keep Stefán in a good mood.

Can you help Eva find the way from Vestmannaeyjar to Egilsstaðir using the least amount of single-lane bridges?

Input

On the first line there are two integers, $2 \leq n \leq 10^5$, the number of locations, and $n-1 \leq m \leq \min {(2\cdot 10^5, n(n-1)/2)}$, the number of roads. Next there are $m$ lines, each with three integers $1 \leq a, b \leq n$ and $c \in \{ 0, 1\} $ which means there is a road between location $a$ and location $b$ which contains a single-lane bridge if $c = 1$ but a double-lane bridge if $c = 0$. Vestmannaeyjar will always be location $1$ and Egilstaðir location $n$. You can assume Iceland’s road system is connected, i.e. it’s possible to get from any location to any other. You can also assume that any pair $a, b$ appears at most once in the input.

Output

One line containing the minimal number of single-lane bridges Stefán and Eva have to cross to get to their destination.

Scoring

Group

Points

Constraints

1

20

$1 \leq n \leq 100$, $n = m$, Iceland’s road system consists of a single cycle of single-lane bridges ($c = 1$)

2

20

$1 \leq n \leq 100$, all roads contain a single-lane bridge ($c = 1$)

3

20

$1 \leq n \leq 100$

4

20

All roads contain a single-lane bridge ($c = 1$)

5

20

No further constraints

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

Please log in to submit a solution to this problem

Log in