暂无测试数据。

蒜头君来到一个巨大的游乐场，这里有 $n$ 个景点。景点和景点之间不能步行，只能乘坐指定的游览车。游览车的数量是无限的，只要你想乘坐就能瞬间出发。现在有 $m$ 种类型的游览车，每种游览车只能在固定的两个景点 $u$ 和 $v$ 之间来回运作，每一趟消耗的时间为 $w$。蒜头君现在在 $1$ 号景点，他想去 $n$ 号景点，请你计算最短需要花费多少时间。

输入格式

第一行两个整数 $n,m\ (1\le n \le 2500,1\le m \le 2\times 10^5)$，分别表示景点数量和游览车数量。

接下来 $m$ 行，每行三个整数 $u,v,w\ (1\le u,v\le n,1\le w\le 10^5,u\neq v)$，表示每种游览车连接的两个景点，和一趟运输所需的时间。

输出格式

输出一个整数，表示最短的时间。如果无法到达 $n$ 号景点，输出 $-1$。

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

11