2357: Dijkstra(II)

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:32 解决:14

题目描述

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

输入

第一行两个整数n,m,代表点数和边数;
接下来m行,每行三个整数s,t,d,代表从s到t有一条长度为d的无向边。

输出

输出一个整数表示最短距离。

样例输入 复制

2 3
1 2 1
1 2 3
2 2 0

样例输出 复制

1

提示

N≤100000,M≤200000,1≤S,T≤N,0≤D≤109