[JOI Open 2022] 放学路（School Road）

**译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T3. [通学路](https://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/school_road/2022-open-school_road-statement.pdf) / [School Road](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/school_road/2022-open-school_road-statement-en.pdf)。** ---- 在洛谷上，本题测试点和子任务配置可能导致评测结果页面难以理解。具体地，将评测结果页面中的子任务编号 $x$ 转为二进制后，从低到高第 $i$ 位为 $1$ 就表示子任务内所有测试点均满足题目中的子任务 $i$ 的限制。

河狸国由 $N$ 座城市组成，编号为 $1 \sim N$。共有 $M$ 条道路连接这些城市，道路编号为 $1 \sim 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$ 行，第 $i$ 行三个正整数 $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

**【样例解释 \#1】** 在这组样例中，从城市 $1$（Bitaro 家）到城市 $4$（学校）的最短距离是 $5$。 有两条到 Bitaro 家并且不经过同一座城市多于一次的路径。 - 按顺序经过道路 $3 \to 1$，长度为 $5$ 的路径，按 $4 \to 2 \to 1$ 的顺序经过城市。 - 按顺序经过道路 $4 \to 2$，长度为 $5$ 的路径，按 $4 \to 3 \to 1$ 的顺序经过城市。 因为不存在到 Bitaro 家的，长度大于 $5$ 且不经过同一座城市多于一次的路径，因此输出 $0$。 这组样例满足所有子任务的限制。 ---- **【样例解释 \#2】** 在这组样例中，从城市 $1$（Bitaro 家）到城市 $4$（学校）的最短距离是 $5$。 有两条到 Bitaro 家并且不经过同一座城市多于一次的路径。 - 按顺序经过道路 $3 \to 1$，长度为 $5$ 的路径，按 $4 \to 2 \to 1$ 的顺序经过城市。 - 按顺序经过道路 $4 \to 2$，长度为 $6$ 的路径，按 $4 \to 3 \to 1$ 的顺序经过城市。 因为存在到 Bitaro 家的，长度大于 $5$ 且不经过同一座城市多于一次的路径，因此输出 $1$。 这组样例满足所有子任务的限制。 ---- **【样例解释 \#3】** 这组样例满足子任务 1、2、3、5 的限制。 ---- **【样例解释 \#4】** 这组样例满足所有子任务的限制。 ---- **【样例解释 \#5】** 这组样例满足子任务 1、2、3、5 的限制。 ---- **【数据范围】** **本题采用捆绑测试。** - 子任务 1（7 分）：$M \le 40$。 - 子任务 2（15 分）：$N \le 18$。 - 子任务 3（23 分）：$M - N \le 13$。 - 子任务 4（35 分）：对于任意三座不同的城市 $a, b, c$，均存在一条从城市 $a$ 到城市 $c$ 且不经过城市 $b$ 的路径。 - 子任务 5（20 分）：无特殊限制。 对于所有数据，满足 $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$，保证经过一定数量的道路，均可以从任意一个城市到达任意其他城市。