P3020 [USACO11MAR] Package Delivery S

题目描述

有一个 $n$ 个点 $m$ 条边的无向图，请求出从 $1$ 到 $n$ 的最短路长度。

输入格式

第一行四个正整数 $n \ m(1 \le n ,m \le 50000)$。 接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接 $u,v$，长为 $w(1 \le w \le 1000$ 的边。

输出格式

输出一行一个整数，表示答案。

输入输出样例 #1

输入 #1

6 8 
4 5 3 
2 4 0 
4 1 4 
2 1 1 
5 6 1 
3 6 2 
3 2 6 
3 4 4

输出 #1

5