1817. 最短路径

输入格式

第一行有 2 个整数 $n,m$ $(0<m\le \frac{n(n-1)}{2})$，接下来 $m$ 行每行有三个整数 $u,v,w$ 结点 $u$ 到 $v$ 有一条权为 $w$ 的边 $(w<{10}^6)$。

输出格式

输出结点 $1$ 到结点 $n$ 之间的最短路径，如果 $1$ 到 $n$ 之间不存在路径，输出 $-1$。

3 3
1 2 10
2 3 15
1 3 30

25