#A1018. 输入法去北极

    ID: 1706 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>算法基础贪心搜索深度优先搜索图论最短路最小生成树

输入法去北极

题目背景

由于输入法十分的不听话,被 xxs 送到了北极

送货员:怎么进来的?

xxs:我想输入“收到”,他给我输出“受刀”,我真是受够他了

输入法:《世界孤立我任他奚落》

送货员:有这么几个路线我咋走划算啊,我生活费没多少了

xxs: 你自己像这般吧(输入法又双叒叕捣乱)

题目描述

为了快速把输入法送到北极,途中有 mm 条线路,有 nn 个中转站,只有到了中转站才可以转换路线,而且每条路线所需话费的钱数也不同

求始发点到北极花费最少的路线所需钱数

输入格式

输入一行 nn mm,表示中转站的点数和线路条数 后 mm 行,每行一个 x,y,zx, y, z,表示 xx 中转站到 yy 中转站的路线需 zz 元钱

输出格式

输出一行,求始发点到北极花费最少的路线所需钱数

当然,最后的中转站也就是所谓的“北极”

样例

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

提示

  • 1n1031\le n\le 10^3
  • 1n1041\le n\le 10^4
  • 1xn1\le x\le n
  • 1yn1\le y\le n
  • 1z1041\le z\le 10^4