Problem Description

In the Beaver Country, there are $N$ cities numbered from $1$ to $N$. There are $M$ roads connecting these cities, numbered from $1$ to $M$. Road $i$ (for $1 \le i \le M$) connects cities $A_i$ and $B_i$ bidirectionally, and its length is $C_i$. It is guaranteed that one can travel from any city to any other city through a certain number of roads.

Bitaro is a beaver living in city $1$. He needs to go to city $N$ for school. Usually, he takes the same route to school, which satisfies the following conditions:
- Let $L$ be the shortest distance from city $1$ to city $N$.
- Bitaro's school route is a path connecting city $1$ and city $N$ with a length of $L$.

Today, due to good weather, Bitaro decides to take a detour home. That is, he will choose a path from city $N$ to city $1$ with a length greater than $L$. Since Bitaro easily gets bored, he does not want to pass through the same city more than once. Therefore, when taking a detour home, he is not allowed to pass through the same city more than once and is not allowed to backtrack.

Given the information about the cities and roads in Beaver Country, write a program to determine if there exists a detour path from school to Bitaro's home.

Reminder during the contest: Bitaro is not allowed to pass through the same city more than once on his way home, but it is not prohibited to pass through cities that are on his usual school route.

Input Format

The first line contains two positive integers $N$ and $M$.

The next $M$ lines contain three positive integers each: $A_i$, $B_i$, and $C_i$.

Output Format

Output a single line with a single number. If there exists a path to Bitaro's home with a length greater than $L$ and without passing through the same city more than once, output $1$; otherwise, output $0$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0

Input Sample #2

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

Output Sample #2

1

Input Sample #3

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

Output Sample #3

0

Input Sample #4

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

Output Sample #4

1

Input Sample #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

Output Sample #5

0

Notes

[Sample Explanation #1]

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

There are two paths to Bitaro's home that do not pass through the same city more than once:
- A path through roads $3 \to 1$ with a length of $5$, passing through cities in the order $4 \to 2 \to 1$.
- A path through roads $4 \to 2$ with a length of $5$, passing through cities in the order $4 \to 3 \to 1$.

Since there is no path to Bitaro's home with a length greater than $5$ and without passing through the same city more than once, the output is $0$.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #2]

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

There are two paths to Bitaro's home that do not pass through the same city more than once:
- A path through roads $3 \to 1$ with a length of $5$, passing through cities in the order $4 \to 2 \to 1$.
- A path through roads $4 \to 2$ with a length of $6$, passing through cities in the order $4 \to 3 \to 1$.

Since there is a path to Bitaro's home with a length greater than $5$ and without passing through the same city more than once, the output is $1$.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks 1, 2, 3, and 5.

[Sample Explanation #4]

This sample satisfies the constraints of all subtasks.

[Sample Explanation #5]

This sample satisfies the constraints of subtasks 1, 2, 3, and 5.

[Data Range]

This problem is bundled test.

• Subtask 1 (7 points): $M \le 40$.
• Subtask 2 (15 points): $N \le 18$.
• Subtask 3 (23 points): $M - N \le 13$.
• Subtask 4 (35 points): For any three distinct cities $a, b, c$, there exists a path from city $a$ to city $c$ that does not pass through city $b$.
• Subtask 5 (20 points): No additional constraints.

For all data, it is guaranteed that $2 \le N \le 10^5$, $1 \le M \le 2 \times 10^5$, $1 \le A_i < B_i \le N$, $1 \le C_i \le 10^9$, and that one can travel from any city to any other city through a certain number of roads.

见题面 Input 部分

见题面 Output 部分