#P2299. Mzc和体委的争夺战
Mzc和体委的争夺战
题目背景
mzc 与 djn 第四弹。
题目描述
mzc 家很有钱(开玩笑),他家有 个男家丁(做过前三弹的都知道)。但如此之多的男家丁吸引来了我们的体委(矮胖小伙),他要来与 mzc 争夺男家丁。
mzc 很生气,决定与其决斗,但 cat 的体力确实有些不稳定,所以他需要你来帮他计算一下最短需要的时间。
输入格式
第一行有两个数 表示有 个停留站,m表示共有m条路。
之后 行,每行三个数 ,表示第 个停留站到第 个停留站需要 的时间。注意,这是双向的。也就是说,从 个停留站到第 个停留站也需要 的时间。
输出格式
一行,输出 到 最短时间。
5 8
1 2 3
2 3 4
3 4 5
4 5 6
1 3 4
2 4 7
2 5 8
1 5 100
11
提示
,,。
由于 mzc 大大十分着急,所以他只能等待 1s。