School Road

Time limit2sMemory limit1024 MB

Summary

Given a weighted connected graph and shortest distance L from city 1 to city N, decide whether a simple path from N back to 1 longer than L exists.

Level: Medium7 of 10
Topics: Shortest path, Graph, DFS
Solved: No attempts yet

Problem

Beaverland consists of $N$ cities, numbered from $1$ to $N$ . There are $M$ roads connecting cities, numbered from $1$ to $M$ . Road $i$ ( $1 \le i \le M$ ) connects city $A_i$ and city $B_i$ in both directions, and its length is $C_i$ . You can travel from any city to any other city by passing through some number of roads.

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

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

Today is a fine day, so Bitaro decides to take a roundabout way home. He will take a route from city $N$ to city $1$ that is longer than $L$ . Bitaro gets bored easily, so he does not want to visit the same city more than once. On the way home, he may not visit the same city twice, and he may not turn back.

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

Input

The first line contains $N$ and $M$ .

$A_1$ $B_1$ $C_1$

$A_2$ $B_2$ $C_2$

$\vdots$

$A_M$ $B_M$ $C_M$

Output

Write one line. Print $1$ if there is a route from city $N$ to city $1$ that is longer than $L$ and visits no city more than once. Otherwise, print $0$ .

Constraints

$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$ ).
You can travel from any city to any other city by passing through some number of roads.

Examples5

Example 1
Input
```
4 4
1 2 1
1 3 2
2 4 4
3 4 3
```
Expected output
```
0
```
Example 2
Input
```
4 4
1 2 1
1 3 3
2 4 4
3 4 3
```
Expected output
```
1
```
Example 3
Input
```
3 4
1 2 1
1 2 2
1 3 3
1 3 3
```
Expected output
```
0
```
Example 4
Input
```
4 5
1 2 1
1 3 2
2 4 4
3 4 3
2 3 1
```
Expected output
```
1
```

Example 5

Input

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

Expected output