등굣길

베이버랜드는 $N$개의 도시로 이루어져 있으며, 도시에는 $1$번부터 $N$번까지 번호가 붙어 있다. 도로는 $M$개이고, $1$번부터 $M$번까지 번호가 붙어 있다. $i$번 도로($1 \le i \le M$)는 도시 $A_i$와 도시 $B_i$를 양방향으로 잇고, 길이는 $C_i$이다. 여러 도로를 거치면 어느 도시에서든 다른 도시로 이동할 수 있다.

비타로는 도시 $1$에 사는 비버이다. 그는 도시 $N$에 있는 학교에 다닌다. 평소에는 학교에 갈 때 항상 같은 길을 이용한다. 이 길은 다음 조건을 만족한다.

• $L$을 도시 $1$에서 도시 $N$까지의 최단 거리라고 한다.
• 비타로의 등굣길은 도시 $1$과 도시 $N$을 잇고, 길이가 $L$이다.

오늘은 날씨가 좋아서 비타로는 돌아가는 길을 우회하기로 했다. 즉, 도시 $N$에서 도시 $1$까지 길이가 $L$보다 긴 경로를 택한다. 비타로는 쉽게 지루해하기 때문에 같은 도시를 두 번 이상 방문하지 않으려 한다. 따라서 우회로에서는 같은 도시를 두 번 방문할 수 없고, 도중에 되돌아갈 수도 없다.

도시와 도로 정보가 주어졌을 때, 학교에서 비타로의 집으로 가는 우회로가 있는지 판단하는 프로그램을 작성하라.

첫 줄에 $N$과 $M$이 주어진다.

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

한 줄에 출력한다. 도시 $N$에서 도시 $1$로 가는 경로 중 길이가 $L$보다 길고 같은 도시를 두 번 이상 방문하지 않는 경로가 있으면 $1$을, 없으면 $0$을 출력한다.

• $2 \le N \le 100\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$).
• $1 \le C_i \le 1\,000\,000\,000$ ($= 10^9$) ($1 \le i \le M$).
• 어느 도시에서든 여러 도로를 거쳐 다른 도시로 이동할 수 있다.