#P2299. Mzc和体委的争夺战

Mzc和体委的争夺战

题目背景

mzc 与 djn 第四弹。

题目描述

mzc 家很有钱(开玩笑),他家有 nn 个男家丁(做过前三弹的都知道)。但如此之多的男家丁吸引来了我们的体委(矮胖小伙),他要来与 mzc 争夺男家丁。

mzc 很生气,决定与其决斗,但 cat 的体力确实有些不稳定,所以他需要你来帮他计算一下最短需要的时间。

输入格式

第一行有两个数 n,m.nn,m.n 表示有 nn 个停留站,m表示共有m条路。

之后 mm 行,每行三个数 ai,bi,cia_i,b_i,c_i,表示第 aia_i 个停留站到第 bib_i 个停留站需要 cic_i 的时间。注意,这是双向的。也就是说,从 bib_i 个停留站到第 aia_i 个停留站也需要 cic_i 的时间。

输出格式

一行,输出 11nn 最短时间。

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

提示

1n25001\le n \leq 25001m2×1051\le m \leq 2\times10^51ci1061\le c_i\le 10^6

由于 mzc 大大十分着急,所以他只能等待 1s。