가중치 복사 버그

$N$개의 정점과 $M$개의 양방향 간선으로 이루어진 그래프가 있다. 정점에는 $1$부터 $N$까지 번호가 매겨져 있다. 각 간선에는 가중치가 있으며, 가중치는 $0$ 또는 $1$이다. 정점 $s$에서 정점 $e$까지 가는 가능한 모든 경로의 길이 중 최솟값을 구하여라.

위 문제는 전형적인 0-1 BFS 문제라서 너무 쉽다. 하지만 아래와 같이 그래프에 가중치 복사 버그가 일어난다면 어떨까?

• 가중치가 $c$인 간선을 지나면, 그 직후 모든 간선의 가중치가 $c$만큼 증가한다.
• 여기서 가중치는 간선의 초기 가중치가 아니라, 간선을 지나기 직전의 가중치이다.

첫째 줄에 정점의 수 $N$, 간선의 수 $M$, 시작 정점의 번호 $s$, 도착 정점의 번호 $e$가 공백으로 구분되어 주어진다. ($2\le N\le 300\,000$; $1\le M\le 600\,000$; $1\le s,e\le N$; $s\ne e$)

이후 $M$개의 줄에 각 간선의 정보가 주어진다. 각 줄에는 $u$, $v$, $c$가 공백으로 구분되어 주어진다. ($1\le u,v\le N$; $u\ne v$; $c\in\{0,1\}$) 이는 정점 $u$와 $v$를 잇고 초기 가중치가 $c$인 간선이 있다는 뜻이다.

$s$에서 $e$로 가는 경로가 적어도 하나 있다.

정점 $s$에서 정점 $e$로 가는 가능한 모든 경로의 길이 중 최솟값을 출력한다.

답은 이진수로 출력하며, 답이 $0$인 경우에는 0을 출력한다. 그렇지 않은 경우에는 0으로 시작하면 안 된다.