Background

Translated from JOI Open 2022 T3. 通学路 / School Road.

On Luogu, the configuration of test points and subtasks for this problem may make the judging result page hard to understand. Specifically, convert the subtask number $x$ shown on the result page into binary. From low to high, if the $i$-th bit is $1$, it means that all test points in that subtask satisfy the constraints of subtask $i$ in the statement.

Background

Translated from JOI Open 2022 T3. 通学路 / School Road.

On Luogu, the configuration of test points and subtasks for this problem may make the judging result page hard to understand. Specifically, convert the subtask number $x$ shown on the result page into binary. From low to high, if the $i$-th bit is $1$, it means that all test points in that subtask satisfy the constraints of subtask $i$ in the statement.

Problem Description

Beaverland consists of $N$ cities, numbered $1 \sim N$. There are $M$ roads connecting these cities, numbered $1 \sim M$. Road $i$ ($1 \le i \le M$) connects cities $A_i$ and $B_i$ in both directions, and the length of road $i$ is $C_i$. It is guaranteed that, by traveling along some number of roads, you can reach any city from any other city.

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

• Let $L$ be the shortest distance from city $1$ to city $N$.
• Bitaro's route to school is a path connecting city $1$ and city $N$ whose total length is $L$.

Because the weather is nice today, Bitaro decides to take a detour on the way home. That is, he will choose a path from city $N$ to city $1$ whose length is greater than $L$. Since Bitaro gets bored easily, he does not want to pass through the same city more than once. Therefore, when he takes a detour home, he is not allowed to pass through the same city more than once, and he is not allowed to go back along the same road segment (i.e. no backtracking).

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

Contest note: Bitaro is not allowed to pass through the same city more than once on the way home, but it is not forbidden to pass through cities that appear in his route to school.

Input Format

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

The next $M$ lines describe the roads. The $i$-th of these lines contains three positive integers $A_i, B_i, C_i$.

Output Format

Output one line with one integer. If there exists a path to Bitaro's home whose length is greater than $L$ and that does not pass through the same city more than once, output $1$; otherwise output $0$.

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

0

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

1

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

0

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

1

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

0

Hint

Sample Explanation #1

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

There are two paths to Bitaro's home that do not pass through the same city more than once.

• A path of length $5$ that uses roads in the order $3 \to 1$, and passes through the cities in the order $4 \to 2 \to 1$.
• A path of length $5$ that uses roads in the order $4 \to 2$, and passes through the cities in the order $4 \to 3 \to 1$.

Since there is no path to Bitaro's home with length greater than $5$ that does not pass through the same city more than once, output $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$ (the school) is $5$.

There are two paths to Bitaro's home that do not pass through the same city more than once.

• A path of length $5$ that uses roads in the order $3 \to 1$, and passes through the cities in the order $4 \to 2 \to 1$.
• A path of length $6$ that uses roads in the order $4 \to 2$, and passes through the cities in the order $4 \to 3 \to 1$.

Since there exists a path to Bitaro's home with length greater than $5$ that does not pass through the same city more than once, output $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.

Constraints

This problem uses bundled tests.

• 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 testdata, $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$. It is guaranteed that, by traveling along some number of roads, you can reach any city from any other city.

Translated by ChatGPT 5