### 问题描述 给定一张 $n$ 个点 $m$ 条边的有向图，该图可以有自环与重边。 你需要输出 $1$ 号点到 $n$ 号点的最短路，若不存在此最短路，输出 `-1`。 ### 输入格式 第一行输入二个正整数 $n,m$。 接下来 $m$ 行，每行输入 $3$ 个正整数 $a,b,c$。表示点 $a$ 到点 $b$ 存在一条有向边，权值为 $c$。 $2\le n\le 500,1\le m\le 10^5,1\le a,b\le n,1\le c\le 10^4$。 ### 输出格式 输出 $1$ 号点到 $n$ 号点的最短路，若不存在此最短路，输出 `-1`。 ### 样例输入 ```text 5 8 1 4 5 2 4 7 3 5 8 1 3 8 5 1 12 4 2 7 4 5 10 2 5 3 ``` ### 样例输出 ```text 15 ``` ### 说明  看图可知最短路为 `[1,4,2,5]`。