#A1018. 输入法去北极
输入法去北极
题目背景
由于输入法十分的不听话,被 xxs 送到了北极
送货员:怎么进来的?
xxs:我想输入“收到”,他给我输出“受刀”,我真是受够他了
输入法:《世界孤立我任他奚落》
送货员:有这么几个路线我咋走划算啊,我生活费没多少了
xxs: 你自己像这般吧(输入法又双叒叕捣乱)
题目描述
为了快速把输入法送到北极,途中有 条线路,有 个中转站,只有到了中转站才可以转换路线,而且每条路线所需话费的钱数也不同
求始发点到北极花费最少的路线所需钱数
输入格式
输入一行 ,表示中转站的点数和线路条数 后 行,每行一个 ,表示 中转站到 中转站的路线需 元钱
输出格式
输出一行,求始发点到北极花费最少的路线所需钱数
当然,最后的中转站也就是所谓的“北极”
样例
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