题目描述(ID:12184)
标题: 游览农场
标签: 图结构 最短路 网络流
详情:
农民约翰的朋友想要访问约翰的农场。于是约翰带他们出去转转。他的农场划分出了N块区域(1<=n<=1000),编号为12~n1号与区域是约翰的住所。而N号区域有一个巨大的谷仓。一共有m(1 <= M <= 10000条双向道路连接这些区域,每条路的长度不会超过35000。为了更好的展示农场,约翰希望从1号区域走到N号区域,然后在返回到1号区域,他希望整个行程的路程最短,而且不能经过同一条路两次。当然约翰确定这样的路径一直是存在的。
输入格式:
第一行输入两个整数n和m
接下来m行每行有三个整数,分别表示起点、终点,以及长度
输出格式:
输一个整数为最短路径长度
样例:

输入

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

输出

6
登录并解答