题目描述

朴素版本正权最短路：

给定一个 $n$ 个点，$m$ 条边的有向图，求 $1$ 到 $n$ 的最短路。

图中可能存在重边和自环。

样例输入

第一行由空格隔开的整数 $n,\ m$。

之后的 $m$ 行，每行三个正整数 $s_i,\ t_i,\ w_i$，表示一条从 $s_i$ 到 $t_i$ 长度为 $w_i$ 的边。

样例输出

一个整数表示从 $1$ 到 $n$ 的最短路长度。

如果不存在最短路，则输出$-1$。

样例

3 3
1 2 2
2 3 1
1 3 4

3

数据范围

$1 \le n \le 500$。

$1 \le m \le n^2$。

图中涉及边长均不超过 $10^{4}$，保证边权为正数。