Description

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

Input

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

Output

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

Sample

Input

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

Output

6