题目描述

你的电子日历包含一个错误$\red{--}$就是我们俗称的 $\red{bug}$。因为这个 $\red{bug，}$偶数不能输入到 日历里。

你正在计划从 $\red{Bytetown }$出差去 $\red{Bitcity}$。很显然，你想要走最短的路程。在你回来之 后，你要把这次的行程长度输入到日历里，所以长度必须是一个奇数。

考虑到 $\red{bug }$会存在很长时间，而且 $\red{Bytetown }$的道路系统很可能会重建很多次，你决定 编写一个程序来帮助你解决将来可能遇到的类似问题。

编写程序解决： 读入 $\red{Byteland }$的地图描述.计算并输出从 $\red{Bytetown }$到 $\red{Bitcity }$的最短奇数长度路径 或者 判断这样的路径是否存在。

输入格式

输入文件第一行包含两个被空格分开的整数 $\red{n }$和 $\red{m（}$$\red{2<=n<=200000,0<=m<=500000）}$，分 别表示城市的数量和道路的数量。

城市从 $\red{1 }$到 $\red{n }$编号，其中 $\red{Bytetown }$编号为 $\red{1，}$$\red{Bitcity }$编号为 $\red{n}$。

接下来 $\red{m }$行描述道路系统。每行包含三个整数 $\red{a，}$$\red{b，}$$\red{c（}$$\red{1<=a,b<=N，}$$\red{a<>b，}$$\red{1<=c<=1000）}$

表示从城市 $\red{a }$到城市 $\red{b }$有一条长度为 $\red{c }$的双向边。

输出格式

输出文件包含一个整数$\red{--}$最短奇数路径长度。

计算出的路径可以访问每个城市和道路多次。只能在城市进行方向转变（包括调头）。

如果不存在这样的路径，输出 $\red{0}$。

样例

输入样例

6 7

1 2 1

2 6 1

1 3 1

5 6 1

3 5 2

3 4 1

5 4 4

输出样例

7