#描述#
公园里有n个景点，编号为1到n，还有m条路径，每条路径连接着两个不同的景点。现要你从景点1出发到达景点n，再返回到景点1，每条路径最多只能走一遍，问你最短所需的总路径长度。

#格式#
##输入格式##
输入包含多组测试数据。
每组测试数据的第一行包含两个整数n、m，分别表示景点数和路径数。
接下来有m行，每行包含三个整数a、b、c，表示景点a和景点b之间有一条路径，长度为c
（1&lt=n&lt=1000,1&lt=m&lt=10000
1&lt=a,b&lt=n,0&ltc&lt=35000）。

##输出格式##
针对每组测试数据，输出所需的最短总长度。

#样例1#
##样例输入1##

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

##样例输出1##

6

#限制#
1000ms
65536KB

#提示#

#来源#