Source : 长沙市雅礼中学屈运华
Description

你的电子日历包含一个错误——就是我们俗称的 bug。因为这个 bug,偶数不能输入到日历里。

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

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

编写程序解决:

读入 Byteland 的地图描述。计算并输出从 Bytetown 到 Bitcity 的最短奇数长度路径或者 判断这样的路径是否存在。

Input

输入文件第一行包含两个被空格分开的整数 n 和 m(2<=n<=200000,0<=m<=500000),分别表示城市的数量和道路的数量。城市从 1 到 n 编号,其中Bytetown 编号为 1, Bitcity 编号为 n。接下来 m 行描述道路系统。每行包含三个整数 a,b,c(1<=a,b<=N,a<>b,1<=c<=1000)表示从城市 a 到城市 b 有一条长度为 c 的双向边。

Output

输出文件包含一个整数——最短奇数路径长度。

计算出的路径可以访问每个城市和道路多次。只能在城市进行方向转变(包括调头)。如果不存在这样的路径,输出 0。

Sample Input
6 7
1 2 1
2 6 1
1 3 1
5 6 1
3 5 2
3 4 1
5 4 4
Sample Output
7