#119. 单源最短路

内存限制
512 MiB
时间限制
2000 ms
标准输入输出
题目类型
传统
评测方式
文本比较
上传者 admin
题目来源 loj

显示标签

题目描述

给一个 个点 条边的无向图,求 的最短路。

输入格式

第一行四个由空格隔开的整数
之后的 行,每行三个正整数 ,表示一条从 长度为 的边。

输出格式

一个整数表示从 的最短路长度。数据保证至少存在一条道路。

样例

输入 #1

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出 #1

7