#P2292. 【POJ Challenge 】永远挑战

【POJ Challenge 】永远挑战

题目描述

lqp18_31 和 1tthinking 经常出题来虐 ftiasch。

有一天,lqp18_31 搞了一个有向图,每条边的长度都是 11。他想让 ftiasch 求出点 11 到点 nn 的最短路。"水题啊。",ftiasch 这么说道。

所以 1tthinking 把某些边的长度增加了 11(也就是说,每条边的长度不是 11 就是 22)。现在,可怜的 ftiasch 要向你求助了。

输入格式

第一行两个整数 n,mn,m 表示点和边的数量。

接下来 mm 行每行三个整数 u,v,wu,v,w,表示一条从 uu 到 vv,边权是 ww 的有向边。

输出格式

一个整数,表示点 11 到点 nn 的最短路。数据保证至少存在一条路径。

3 3
1 2 1
2 3 1
1 3 2
2

数据规模与约定

对于 100%100\% 的数据,1≤u,v≤n≤1051\leq u,v\leq n\leq 10^5,1≤m≤1061\leq m\leq 10^6,1≤w≤21\leq w\leq 2。