Beaverland 由 $N$ 个城市组成，编号为 $1$ 到 $N$。有 $M$ 条道路连接这些城市，编号为 $1$ 到 $M$。第 $i$ 条道路（$1 \le i \le M$）双向连接城市 $A_i$ 和城市 $B_i$，其长度为 $C_i$。可以通过若干条道路从任意城市到达其他任意城市。

Bitaro 是一只住在城市 $1$ 的海狸。他要去城市 $N$ 的学校。他通常走同一条路线去学校。他去学校的路线满足以下条件： 设 $L$ 为从城市 $1$ 到城市 $N$ 的最短距离。 Bitaro 去学校的路线连接城市 $1$ 和城市 $N$，且其长度为 $L$。

由于今天天气晴朗，Bitaro 决定绕路回家。也就是说，他将走一条从城市 $N$ 到城市 $1$、长度大于 $L$ 的路线。由于 Bitaro 很容易感到厌烦，他不想多次访问同一个城市。因此，当他绕路回家时，不允许多次访问同一个城市，也不允许在途中折返。

给定 Beaverland 的城市和道路信息，编写一个程序，判断是否存在一条从学校到 Bitaro 家的绕路。

输入格式

从标准输入读取以下数据。给定值均为整数。

$N \ M$

$A_1 \ B_1 \ C_1$

$A_2 \ B_2 \ C_2$

$\vdots$

$A_M \ B_M \ C_M$

输出格式

向标准输出写入一行。如果存在一条到 Bitaro 家的、长度大于 $L$ 且不重复访问同一个城市的路线，则输出 $1$。否则，输出 $0$。

数据范围

• $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$)。
• 可以通过若干条道路从任意城市到达其他任意城市。

子任务

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$ 分) 无附加限制。

样例

输入格式 1

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

输出格式 1

0

说明

在该样例中，从城市 $1$（Bitaro 的家）到城市 $4$（学校）的最短距离为 $5$。存在两条不重复访问同一个城市的回家路线： 一条长度为 $5$ 的路线，依次经过道路 $3 \to 1$，依次访问城市 $4 \to 2 \to 1$。 一条长度为 $5$ 的路线，依次经过道路 $4 \to 2$，依次访问城市 $4 \to 3 \to 1$。 由于不存在长度大于 $5$ 且不重复访问同一个城市的回家路线，输出 $0$。

输入格式 2

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

输出格式 2

1

说明

在该样例中，从城市 $1$ 到城市 $4$ 的最短距离为 $5$。存在两条不重复访问同一个城市的回家路线： 一条长度为 $5$ 的路线，依次经过道路 $3 \to 1$，依次访问城市 $4 \to 2 \to 1$。 一条长度为 $6$ 的路线，依次经过道路 $4 \to 2$，依次访问城市 $4 \to 3 \to 1$。 由于存在一条长度大于 $5$ 且不重复访问同一个城市的回家路线，输出 $1$。

输入格式 3

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

输出格式 3

0

输入格式 4

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

输出格式 4

1

输入格式 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

输出格式 5

0