问题描述

给定一张 $n$ 个点、$m$ 条无向边 的简单图，点的编号从 $1$ 到 $n$。

每条边的边权只有两种可能：$0$ 或 $1$。

请你求出从 $1$ 号点到 $n$ 号点 的最短路径长度（即路径上所有边权之和的最小值）。

如果 $1$ 号点无论如何也无法到达 $n$ 号点，请输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示点数和边数。

接下来 $m$ 行，每行包含三个整数 $u,\ v,\ w$，表示一条连接 $u$ 和 $v$ 的无向边，权重 $w \in \{0, 1\}$。

数据保证没有重边和自环（即 $u \ne v$，同一对点之间最多一条边）。

输出格式

一个整数，表示 $1$ 号点到 $n$ 号点的最短路径长度；若不可达，输出 $-1$。

样例输入 1

3 3
1 2 0
2 3 1
1 3 1

样例输出 1

1

说明：路径 $1 \xrightarrow{0} 2 \xrightarrow{1} 3$，总长度 $1$；直接走 $1 \xrightarrow{1} 3$ 也是 $1$，二者等价。

样例输入 2

4 3
1 2 0
2 3 0
1 4 1

样例输出 2

1

说明：路径 $1 \xrightarrow{0} 2 \xrightarrow{0} 3$ 走不到 $4$；最短是 $1 \xrightarrow{1} 4$，长度 $1$。

样例输入 3

3 1
1 2 0

样例输出 3

-1

说明：$3$ 号点根本进不来任何边，与 $1$ 号点不连通。

说明

• 答案可能为 $0$（例如存在一条全部由 $0$ 边组成的路径）。
• $n = 1$ 时答案为 $0$（已经在终点）。
• 若 $1$ 与 $n$ 不连通，输出 $-1$。

评测数据规模

对于所有数据，保证 $1 \le n \le 100$，$0 \le m \le 5000$，每条边权 $w \in \{0, 1\}$。