절연 구간 최소화

지하철은 직류 또는 교류 방식으로 전기를 공급받는다. 열차가 운행 중에 급전 방식이 바뀌면 잠시 전력 공급이 끊기는데, 이를 절연이라 부른다. 절연이 적게 발생할수록 열차 탑승객의 만족도가 높아진다.

서울특별시에는 $N$개의 지하철역이 있고, 두 역을 직접 잇는 선로가 $M$개 설치되어 있다. 역에는 1번부터 $N$번까지, 선로에는 1번부터 $M$번까지 번호가 붙어 있다. 설치된 선로만으로 임의의 두 역 사이를 이동할 수 있다. 각 선로는 직류 또는 교류 중 하나로 전기를 공급하며, 양방향으로 통행할 수 있다.

열차는 역과 이어진 선로를 따라 다른 역으로 이동하는 과정을 몇 번이든 반복할 수 있다. 이때 이용하는 선로의 급전 방식이 직류에서 교류로, 또는 교류에서 직류로 바뀌면 절연이 발생한다.

당신은 열차 기관사이다. $A$번 역에서 출발해 선로를 따라 $B$번 역까지 열차를 운행하려고 한다. 절연이 가장 적게 일어나는 경로로 운행할 때, 절연이 몇 번 발생하는지 구하시오.

첫 줄에 지하철역의 수 $N$과 선로의 수 $M$이 공백으로 구분되어 주어진다.

다음 $M$개의 줄에는 정수 $S_i$, $E_i$, $T_i$가 공백으로 구분되어 주어진다. 이는 $i$번 선로가 $S_i$번 역과 $E_i$번 역을 직접 연결하며, $T_i = 0$이면 직류, $T_i = 1$이면 교류로 전기를 공급받음을 뜻한다.

마지막 줄에는 시작 역 $A$와 끝 역 $B$가 공백으로 구분되어 주어진다.

$A$번 역에서 $B$번 역까지 열차를 운행할 때, 급전 방식이 바뀌는 최소 횟수를 정수로 출력한다.

• 주어지는 모든 수는 정수이다.
• $2 \le N \le 100000$
• $1 \le M \le 150000$
• $1 \le S_i \le N$
• $1 \le E_i \le N$
• $S_i \ne E_i$
• $T_i = 0$ 또는 $T_i = 1$
• $1 \le A \le N$
• $1 \le B \le N$
• $A \ne B$
• 주어진 선로만으로 임의의 두 역 사이를 이동할 수 있다.
• 두 역을 직접 잇는 선로는 최대 한 개 존재한다.