3118: 小W解谜图
内存限制：256 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：5
解决：3
题目描述
解出谜题的小 W 终于又一次鼓起勇气向小 M 表白，然而却收到了小 M 的谜图：
谜图竟然是约会地图！图中一共有 N 个城市，由 M 条双向路连接。小 W 和小 M 在 1 号城市，约会地点在 N 号城市。
然而为了节约路费，并且小 M 喜欢奇数，小 W 需要找到到 N 号城市的奇数长度的最短路，每条路每个城市可以经过多次。
如果小 W 解不出谜图，小 M 就不接受告白，作为计算机大神的你快帮帮小 W 吧！
输入
第一行两个整数 N,M。
接下来 M 行，每行三个整数 A,B,C，表示 A 城市和 B 城市之间有一条长度为 C 的双向边。
输出
若有存在最短奇数长度路径，则输出，否则输出 0。
数据可能有重边，自环。 保证答案在 maxlongint 之内。
样例输入 复制
6 7
1 2 1
2 6 1
1 3 1
5 6 1
3 5 2
3 4 1
4 5 4样例输出 复制
7提示
【样例解释】
【数据范围】
对于 20%的数据： N<=10,M<=50。
对于 50%的数据： N<=500,M<=5000。
对于 100%的数据： N<=200000,M<=500000。