题目描述

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

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

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

输入格式

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

接下来 $m$ 行每行三个整数 $u,v,w$，表示一条从 $u$ 到 $v$，边权是 $w$ 的有向边。

输出格式

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

3 3
1 2 1
2 3 1
1 3 2

2

数据规模与约定

对于 $100\%$ 的数据，$1\leq u,v\leq n\leq 10^5$，$1\leq m\leq 10^6$，$1\leq w\leq 2$。