最短路(Spfa)

题目描述

给定 M  条边， N  个点的带权无向图。求 1 到 N  的最短路。

输入描述

第一行：N,M(N<=100000，M<=500000) ；

接下来M 行3 个正整数：$a_i,b_i,c_i$表示$a_i,b_i$之间有一条长度为ci的路，$ c_i \leq 1000$ 。

输出描述

一个整数，表示1到N的最短距离。

提示

【样例解释】

注意图中可能有重边和自环,数据保证1到N有路径相连。