题目描述

给你一张简单有向图，边权都为非负整数。请计算从 $1$ 到 $n$ 的最短路。

图用以下形式给出：

第一行输入两个整数 $n,m$，表示图的顶点数、边数，顶点编号从 $1$ 到 $n$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 到 $y$ 有一条有向边，边权为 $z$。

请计算从 $1$ 到 $n$ 的最短路长度，如果无法到达，输出 -1。

输入格式

第一行三个整数 $n,m$，表示图的顶点数、边数。

接下来 $m$ 行，每行有三个整数 $abc$，代表从 $a$ 到 $b$ 有一条长度为 $c$ 的边。

输出格式

一个数表示答案。

3 4
1 3 8
1 2 3
2 3 2
3 2 1

5

数据说明

从 $1$ 到 $3$ 有两条路：

$1→2→3$ 总长度为 $3+2=5$。

$1→3$ 长度为 $8$。

当然你也可以在 $2,3$ 两个点来回转圈，但这显然会越来越长。

数据规模

对于所有数据，保证 $2≤n≤5000,0≤m≤10000,1≤x,y≤n,x≠y,1≤z≤10000$。