题目描述
小明一家到某个景区中旅游,景区里有N个景点分布在景区的不同位置,共有M条边连着里面的景点,某两个景点之间可能有道路相连,道路是可以双向通行的,但是景区要求同一条路只能经过一次,游客可以选择从任意一个景点出发,但是必须从起点的景点结束。由于小明的妈妈已经很累了,她希望能在参观的时候走最少的路,因此请你帮他们求出最短的游览路线
输入描述
输入第一行有两个正整数N和M,两个数字用空格隔开,满足(N<=100)。
接下来M行,每行由3个正整数X,Y,Z组成,分别代表道路两端的景点编号以及道路的长度。(Z<=10000)
输出描述
输出共一行,如果有满足要求的参观路线,则输出参观路线长度,否则输出“No solution.”(不要输出引号)。
样例输入
5 7
1 4 1
1 5 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
样例输出
61
提示