题目描述

著名算法学家罗老师正在参加一场全国巡回的学术舞会。舞会的第 $n$ 站向他发出了最终邀约。罗老师目前身处城市 $1$ 的研究所，他需要规划一条前往城市 $n$ 的路线。

这片区域有 $n$ 个城市，编号从 $1$ 到 $n$。城市之间的交通网络由 $m$ 条双向道路构成。这个网络并非完全连通：有些城市之间由高速公路直接相连，交通便捷；而有些城市之间则没有直达路线，需要绕行。值得注意的是，出于历史或地理原因，某些重要的城市对之间甚至可能存在多条长度不同的直接道路，这为路径规划增加了额外的考量维度。

现在，罗老师拿到了完整的道路数据，每条数据记录了其连接的两个城市编号 $a$, $b$ 以及该条道路的精确长度 $c$。时间紧迫，罗老师需要你帮助他计算：从城市 $1$ 的研究所出发，到达城市 $n$ 的舞会现场，所可能行走的最短距离总和是多少？ 请你设计程序，帮助罗老师找到这条最优路径，或者告诉他这是一个无法完成的任务。

输入格式

第一行包含两个整数 $n$, $m$ $(1 \le n \le 2000,\ 1 \le m \le 10000)$，分别表示城市的数量和道路的数量。

接下来的 $m$ 行，每行包含三个整数 $a$, $b$, $c$ $(1 \le a, b \le n,\ 0 \le c \le 10000)$，表示城市 $a$ 与城市 $b$ 之间存在一条长度为 $c$ 的双向道路。输入数据保证 $a \neq b$。注意：两个城市之间可能存在多条直接相连的道路，其长度可能相同也可能不同。

输出格式

输出一行一个整数，表示从城市 $1$ 到城市 $n$ 的最短距离。

如果从城市 $1$ 出发无法到达城市 $n$（即两个城市在不连通的组件中），则输出 -1。

输入输出样例

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

90

样例1解释： 从城市1到城市n的最短路径是 1 -> 2 -> 3 -> 4 -> 5，路径总长度为 20+30+20+20 = 90。虽然存在从 1 直接到 5 长度为 100 的道路，但并非最短。

2 0

-1

样例2解释： 只有两个城市，且它们之间没有任何道路连接，因此从城市1无法到达城市2，输出 -1。