교량

이미지 출처: Wikimedia Commons

작년의 일로 모두가 알고 있듯이 Eva와 Stefán은 Vestmannaeyjar에 산다. 당시 당신은 Eva가 Stefán과 함께 가능한 한 짧은 시간 안에 나라 전체를 둘러볼 수 있는 최적의 여행 계획을 찾도록 도왔다. 이제 Eva는 다시 Egilsstaðir를 방문하고 싶지만, 나라를 여행하는 동안 그들은 Stefán이 단일 차로 교량을 정말 싫어한다는 사실을 알게 되었다. 그래서 Eva는 Stefán의 기분을 좋게 유지할 수 있도록 도와달라며 다시 당신을 찾아왔다.

Eva가 Vestmannaeyjar에서 Egilsstaðir까지 가는 경로 중 단일 차로 교량을 가능한 한 적게 포함하는 경로를 찾도록 도울 수 있는가?

채점

그룹 | 점수 | 제한

1 | 20 | $1 \leq n \leq 100$, $n = m$, 아이슬란드의 도로망은 단일 차로 교량들로 이루어진 하나의 순환을 형성한다 ($c = 1$)

2 | 20 | $1 \leq n \leq 100$, 모든 도로에는 단일 차로 교량이 포함된다 ($c = 1$)

3 | 20 | $1 \leq n \leq 100$

4 | 20 | 모든 도로에는 단일 차로 교량이 포함된다 ($c = 1$)

5 | 20 | 추가 제한 없음

첫째 줄에 두 정수, 장소의 수 $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$이면 두 차로 교량을 포함한다는 뜻이다. Vestmannaeyjar의 번호는 항상 $1$이고 Egilsstaðir의 번호는 항상 $n$이다. 아이슬란드의 도로망은 연결되어 있다고 가정해도 된다. 즉, 모든 장소에서 다른 모든 장소로 갈 수 있다. 또한 각 쌍 $a, b$은 입력에 최대 한 번만 등장한다고 가정해도 된다.

Stefán과 Eva가 목적지에 도착하기 위해 건너야 하는 단일 차로 교량의 최소 개수를 한 줄에 출력한다.