【题目描述】

给定一个有向连通图，求从 1 到 n 的最短路。

【输入】

第一行两个整数 n, m，代表点数和边数；

接下来 m 行，每行三个整数 s, t, d，代表从 s 到 t 有一条长度为 d 的有向边。

【输出】

输出一个整数，表示从 1 到 n 的最短距离。

【输入样例】

2 3
1 2 1
1 2 -1
2 2 0

【输出样例】

-1

【提示】

数据规模及约定：N≤20000，M≤40000，1≤S,T≤N，−10^9≤D≤10^9。

保证图中没有负环，且 1 可以到达 n。

题面来源：https://blog.csdn.net/lybc2019/article/details/128441900

题目来源：信息学奥赛一本通 1419；数据整理来源：ROJ 1419。