Beaverland consists of $N$ cities, numbered from $1$ to $N$. There are $M$ roads connecting cities, numbered from $1$ to $M$. The road $i$ $(1\le i\le M)$ connects the city $A_i$ and the city $B_i$ bidirectionally, and the length of the road $i$ is $C_i$. It is possible to move from any city to any other city by passing through a number of roads.

Bitaro is a beaver living in the city $1$. He goes to a school in the city $N$. He usually takes the same route to the school. His route to the school satisfies the following conditions.

• Let $L$ be the minimum distance from the city $1$ to the city $N$.
• Bitaro's route to the school connects the city $1$ and the city $N$, and its length is $L$.

Since today is a fine day, Bitaro decided to go back to his home by taking a roundabout way. Namely, he will take a route longer than $L$ from the city $N$ to the city $1$. Since Bitaro is easily bored, he does not want to visit the same city more than once. Therefore, when he takes a roundabout way to his home, it is not allowed to visit the same city more than once, and it is not allowed to turn back on the way.

Given information of the cities and the roads in Beaverland, write a program which determines whether there exists a roundabout way from the school to Bitaro's home.

Input Specification

Read the following data from the standard input. Given values are all integers.

$NM$

$A_1{B}_1{C}_1$

$A_2{B}_2{C}_2$

$⋮$

$A_M{B}_M{C}_M$

Output Specification

Write one line to the standard output. Output $1$ if there exists a route to Bitaro's home longer than $L$ without visiting the same city more than once. Otherwise, output $0$.

Constraints

• $2\le N\le 100000$.
• $1\le M\le 200000$.
• $1\le A_i<B_i\le N$ $(1\le i\le M)$.
• $1\le C_i\le {10}^9$ $(1\le i\le M)$.
• It is possible to move from any city to any other city by passing through a number of roads.

Subtasks

1. (7 points) $M\le 40$.
2. (15 points) $N\le 18$.
3. (23 points) $M-N\le 13$.
4. (35 points) For any distinct cities $a,b,c$, there is a route from the city $a$ to the city $c$ without passing through the city $b$.
5. (20 points) No additional constraints.

Sample Input 1

4 4
1 2 1
1 3 2
2 4 4
3 4 3

Sample Output 1

0

Explanation for Sample 1

In this sample input, the minimum distance from the city $1$ (Bitaro's home) to the city $4$ (school) is $5$.

There are two routes to Bitaro's home without visiting the same city more than once.

• A route of length $5$ passing through the roads $3\to 1$ in this order, and visiting the cities $4\to 2\to 1$ in this order.
• A route of length $5$ passing through the roads $4\to 2$ in this order, and visiting the cities $4\to 3\to 1$ in this order.

Since there does not exist a route to Bitaro's home longer than $5$ without visiting the same city more than once, output $0$.

This sample input satisfies the constraints of all the subtasks.

Sample Input 2

4 4
1 2 1
1 3 3
2 4 4
3 4 3

Sample Output 2

1

Explanation for Sample 2

In this sample input, the minimum distance from the city $1$ (Bitaro's home) to the city $4$ (school) is $5$.

There are two routes to Bitaro's home without visiting the same city more than once.

• A route of length $5$ passing through the roads $3\to 1$ in this order, and visiting the cities $4\to 2\to 1$ in this order.
• A route of length $6$ passing through the roads $4\to 2$ in this order, and visiting the cities $4\to 3\to 1$ in this order.

Since there exists a route to Bitaro's home longer than $5$ without visiting the same city more than once, output $1$.

This sample input satisfies the constraints of all the subtasks.

Sample Input 3

3 4
1 2 1
1 2 2
1 3 3
1 3 3

Sample Output 3

0

This sample input satisfies the constraints of Subtasks 1, 2, 3, 5.

Sample Input 4

4 5
1 2 1
1 3 2
2 4 4
3 4 3
2 3 1

Sample Output 4

1

This sample input satisfies the constraints of all the subtasks.

Sample Input 5

12 17
2 4 656247308
4 6 106088453
1 5 754343261
9 12 497827261
3 8 759830309
3 4 61084725
1 6 324702188
3 6 415317430
7 12 846175092
5 8 278621369
1 10 891247646
10 12 755236904
6 8 511967203
5 6 597197970
1 7 800309458
7 9 348347831
10 11 134217757

Sample Output 5

0

This sample input satisfies the constraints of Subtasks 1, 2, 3, 5.