题目描述

译自 JOI Open 2022 T3 「通学路 / School Road」

河狸国由 $N$ 个城市组成，编号为 $1$ 到 $N$。共有 $M$ 条道路连接这些城市，道路编号为 $1$ 到 $M$。路 $i\ (1\le i\le M)$ 双向连接城市 $A_i$ 和 $B_i$，并且路 $i$ 的长度为 $C_i$。通过一些数量的道路，可以从任意一个城市到达任意其他城市。

Bitaro 是一只住在城市 $1$ 的河狸。他要去城市 $N$ 上学。他上学通常都走一样的路线。他的上学路满足如下条件。

• 令 $L$ 为从城市 $1$ 到城市 $N$ 的最短距离。
• Bitaro 的上学路是一条连接城市 $1$ 和城市 $N$ 且长度为 $L$ 的路径。

因为今天天气好，Bitaro 决定绕路回家。也就是说，他会选择一条从城市 $N$ 到城市 $1$ 且长度大于 $L$ 的路径。因为 Bitaro 很容易厌倦，他不想经过同一个城市多于一次。因此，当他绕远路回家时，不允许经过同一个城市多于一次，并且不允许走回头路。

给定河狸国的城市和道路的信息，写一个程序确定是否存在一条从学校到 Bitaro 的家的远路。

注意：Bitaro 不允许在回家途中经过相同的城市超过一次，但是不禁止经过上学路线中会经过的城市。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行三个整数 $A_i,B_i,C_i$。

输出格式

输出一行。如果存在一条到 Bitaro 家的，长度大于 $L$ 且不经过同一个城市多于一次的路径，输出 $1$，否则输出 $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

数据范围与提示

对于所有数据，$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$，保证通过一些数量的道路，可以从任意一个城市到达任意其他城市。

详细子任务附加限制及分值如下表所示。