【bzoj2292】[POJ Challenge]永远挑战

2014年4月2日1,2700

Description

 

lqp18_31和1tthinking经常出题来虐ftiasch。有一天, lqp18_31搞了一个有向图,每条边的长度都是1。 他想让ftiasch求出点1到点 N 的最短路。”水题啊。”, ftiasch这么说道。

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

 

Input

 

第1行,两个整数 N (1 ≤ N ≤ 105) 和 M (1 ≤ M ≤ 106), 点和边的数量。

第2到 M + 1行: 三个整数 UiViWi (1 ≤ Wi ≤ 2), 从点 Ui 到 Vi 长度为 Wi 的边。

 

Output

 

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

 

Sample Input

3 3
1 2 1
2 3 1
1 3 2

Sample Output

2

题解

如果a到b的边权为2,建一个新的点c,a向c连边,c向b连边