题目描述

优化版本正权最短路：

给定一个 $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 10^{5}$。

$1 \le m \le 2 * 10^{5}$。

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