题目描述

Snuke 的城市有一个地铁系统，由 $N$ 个站点和 $M$ 条铁路线组成。站点编号从 $1$ 到 $N$。每一条线路由一家公司运营。每家公司有一个编号。

第 $i$（$1 \leq i \leq M$）条线路双向连接着站点 $p_i$ 和 $q_i$。没有中间站。该线路由公司 $c_i$ 运营。

你可以在有多条线路的站点换乘。

该地铁系统使用的票价系统有些奇怪。当乘客只使用同一家公司运营的线路时，票价为 1 日元（日本的货币单位）。每当乘客换乘到与当前线路不同公司运营的线路时，需要额外支付 1 日元的票价。如果一个乘客从某家公司 A 的线路换乘到另一家公司的线路，然后再次换乘回公司 A 的线路，还会再次产生额外的票价。

Snuke 此刻在站点 1，想要乘坐地铁前往站点 $N$。找出所需的最低票价。

约束条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 2×10^5$
• $1 \leq p_i \leq N$ ($1 \leq i \leq M$)
• $1 \leq q_i \leq N$ ($1 \leq i \leq M$)
• $1 \leq c_i \leq 10^6$ ($1 \leq i \leq M$)
• $p_i \neq q_i$ ($1 \leq i \leq M$)

输入

从标准输入读入输入数据，输入格式如下：

$N$ $M$

$p_1$ $q_1$ $c_1$

...

$p_M$ $q_M$ $c_M$

输出

输出所需的最低票价。如果无法乘坐地铁到达站点 $N$，打印 -1。

示例输入1

3 3
1 2 1
2 3 1
3 1 2

示例输出1

1

使用公司 1 的线路：1 → 2 → 3。票价为 1 日元。

示例输入2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

示例输出2

2

首先使用公司 1 的线路：1 → 3 → 2 → 5 → 6。然后使用公司 5 的线路：6 → 7 → 8。票价为 2 日元。

示例输入3

2 0

示例输出3

-1