Home => ProblemSet => 一次免费通行
2373: 一次免费通行
Time Limit: 3 Sec Memory Limit: 512 MB Submit: 0 Solved: 3[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]
Description
有n个地点和m条双向道路。第i条道路连接ui与vi，通行费用为wi。
你需要从地点1到达地点n。途中可以选择至多一次道路通行，将这一次的费用改为0。求最小总费用。
你需要从地点1到达地点n。途中可以选择至多一次道路通行，将这一次的费用改为0。求最小总费用。
Input
第一行输入两个整数n,m。
接下来m行，每行输入三个整数ui, vi, wi。
接下来m行，每行输入三个整数ui, vi, wi。
Output
输出一个整数，表示最小总费用。
Sample Input Copy
5 6
1 2 5
2 5 5
1 3 1
3 4 1
4 5 10
2 4 2
Sample Output Copy
2
HINT
样例二：
输入：
4 5
1 2 2
2 4 2
1 3 1
3 4 100
2 3 10
输出：
1
样例一解释：
沿1 -> 3 -> 4 -> 5行走，免费通过4与5之间的道路，总费用为1+1+0=2。
样例二解释：
沿1 -> 3 -> 4行走，免费通过3与4之间的道路，总费用为1。
其他样例下载：road.zip
输入：
4 5
1 2 2
2 4 2
1 3 1
3 4 100
2 3 10
输出：
1
样例一解释：
沿1 -> 3 -> 4 -> 5行走，免费通过4与5之间的道路，总费用为1+1+0=2。
样例二解释：
沿1 -> 3 -> 4行走，免费通过3与4之间的道路，总费用为1。
其他样例下载：road.zip