题目描述

罗老师被邀请参加一个舞会，地点在城市 $n$，而他当前所在的城市为 $1$。附近还有城市 $2 \sim n$，有些城市之间有直接相连的双向道路，有些则没有，且同一个城市对之间可能有多条道路。

现给出所有直接相连道路的长度，罗老师想知道从城市 $1$ 到城市 $n$ 的最短距离是多少。

输入格式

第一行包含两个整数 $n, m$，分别表示城市数量和道路数量。

接下来 $m$ 行，每行包含三个整数 $a, b, c$，表示城市 $a$ 与城市 $b$ 之间有一条长度为 $c$ 的双向道路。

输出格式

输出一个整数，表示从城市 $1$ 到城市 $n$ 的最短距离。如果无法到达，则输出 $-1$。

样例

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

90

数据范围

• $1 \le n \le 2000$
• $1 \le m \le 10000$
• $0 \le c \le 10000$
• 图中可能存在重边。