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

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

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

编写程序解决：

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

输入文件第一行包含两个被空格分开的整数 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 的双向边。

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

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