【POJ Challenge 】永远挑战

lqp18_31 和 1tthinking 经常出题来“虐” ftiasch。有一天，lqp18_31 构造了一个有向图，其中每条边的长度都是 $1$ 。他想让 ftiasch 求出从点 $1$ 到点 $N$ 的最短路。ftiasch 说道：“水题啊。”

于是，1tthinking 将某些边的长度增加了 $1$ ，也就是说，现在每条边的长度不是 $1$ 就是 $2$ 。可怜的 ftiasch 只好向你求助。

时间限制： $10000\ \mathrm{ms}$ 。
内存限制： $131072\ \mathrm{KB}$ 。

输入格式

第 $1$ 行包含两个整数 $N$ 和 $M$ ，分别表示点的数量和边的数量。

接下来 $M$ 行，每行包含三个整数 $U_i$ 、 $V_i$ 和 $W_i$ ，表示存在一条从点 $U_i$ 到点 $V_i$ 的有向边，边长为 $W_i$ 。

输出一个整数，表示从点 $1$ 到点 $N$ 的最短路长度。

数据保证至少存在一条从点 $1$ 到点 $N$ 的路径。

本题为 POJ Challenge 试题「永远挑战」，题面与测试数据整理自 BZOJ 2292。