问题描述

给定一张 $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。

样例输入

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

样例输出

15

说明

看图可知最短路为 [1,4,2,5]。