Background

Special for beginners, ^_^

Description

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

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

Format

Input

第1行，两个整数 N (1 ≤ N ≤ 10 ^5^ ) 和 M (1 ≤ M ≤ 10 ^6^ ), 点和边的数量。

第2到 M + 1行: 三个整数 U~i~ , V~i~ , W~i~ (1 ≤ W~i~ ≤ 2), 从点 U~i~ 到 V~i~ 长度为 W~i~ 的边。

Output

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

Samples

3 3
1 2 1
2 3 1
1 3 2

2

Limitation

1s, 1024KiB for each test case.