本市将举行一场珠宝展览。展览场地很大，有很多房间。有的房间之间通过通道相互连接。以下是展览场地的地图。

　　　　　

　　Rx 表示房间x ，同时连接Ra 和Rb边上的数字表示房间a和房间b之间的距离。

　　为了安全起见，主办者雇用了一队保安。保安将按照计划巡逻。他们将走遍所有的通道并回到出发点。一些通道会被走过几次。他们希望走的路程尽可能短。但是因为地图太复杂，他们无法确定最短的路程，所以他们让你帮忙，希望你写一个程序确定保安走的最短路程。

　　输入

　　输入文件包含多个地图。每个地图的第一行包括两个整数n(n≤100)和m（用空格分隔），n表示房间数，m表示通道的数目。接下来m行描述通道的情况。每一行包括三个整数a,b和d，（用空格分隔），表示房间a和房间b的距离是d。n=0或者m=0表示输入结束。每一行头尾没有多余的空格。地图之间没有多余的空行。

　　输出

　　你的程序应当输出每个地图最短巡逻路径的长度。每个答案占一行，不同地图之间没有空行。

　　Sample Input

　　9 12
　　1 2 5
　　1 8 2
　　2 3 5
　　2 9 6
　　3 4 9
　　4 5 4
　　4 9 4
　　5 6 4
　　6 7 3
　　6 9 4
　　7 8 4
　　8 9 3
　　0 0

　　Sample Output for Sample Input

　　68