你的电子日历中存在一个错误——程序员称之为“Bug”。由于这个 Bug，日历中无法输入偶数。

你正计划从 Bytetown 到 Bitcity 进行一次商务旅行。显然，你希望选择最短路径。旅行结束后，你必须将路径长度输入到日历中，因此该长度必须是一个奇数。

考虑到日历中的这个 Bug 在很长一段时间内都不会被修复，且 Byteland 的道路系统可能会多次重建，你决定编写一个程序来帮助你处理未来类似的问题。

编写一个程序，完成以下任务：

• 从标准输入读取 Byteland 地图的描述；
• 计算从 Bytetown 到 Bitcity 的最短奇数长度路径，如果不存在则进行判断；
• 将结果写入标准输出。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 200\,000$, $0 \le m \le 500\,000$)，由一个空格分隔，分别表示 Byteland 的城市数量和道路数量。城市编号从 $1$ 到 $n$；Bytetown 的编号为 $1$，Bitcity 的编号为 $n$。

接下来的 $m$ 行描述了 Byteland 的道路系统。每行包含三个由空格分隔的整数 $a$、$b$、$c$ ($1 \le a, b \le n$, $a \neq b$, $1 \le c \le 1\,000$)，表示连接城市 $a$ 和 $b$ 的一条长度为 $c$ 的双向道路。

输出格式

输出的第一行且仅有一行包含一个整数，即从 Bytetown 到 Bitcity 的最短奇数长度路径的长度。计算出的路径可以多次经过某些城市和道路。改变行驶方向（包括掉头）只能在城市中进行。如果不存在这样的路径，则输出 $0$。

样例

输入 1

6 7
1 2 1
2 6 1
1 3 1
5 6 1
3 5 2
3 4 1
5 4 4

输出 1

7