2661: 迷宫
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：4
解决：3
题目描述
凯文神父一行人，得到了一张影之国的地图。发现其迷宫很有特色，可以看作是一个由N个节点，M条边组成的有向图，而且每条边的长度只会是1，2个单位。现在他们正处于1号点，而下一个探索目标是N号点。于是他们拜托精于计算的你，帮他们算出1号点到N号点的最短距离。
输入
第1行，两个整数N (1 ≤ N ≤ 105) 和M (1 ≤ M ≤ 106), 点和边的数量。
第2到M + 1行: 三个整数Ui, Vi, Wi (1 ≤ Wi ≤ 2), 从点Ui 到Vi 长度为Wi 的边。
输出
一个整数，表示点1到点N的最短路。数据保证至少存在一条路径。
样例输入 复制
3 3
1 2 1
2 3 1
1 3 2样例输出 复制
2提示
40% 的数据1≤ n≤ 1000
100%的数据. 1 ≤ N ≤ 105，1 ≤ M ≤ 106 。
输入数据可能出现重边和自环。