Description

小明是个爱锻炼的好孩子，每天早晨他都会去自己家附近的一个公园晨跑。这个公园里有若干个花坛，这些花坛由一些小路连接。一天，小明在跑步的过程中突然想到这样一个问题：

如果自己可以选择从任何一个花坛开始，想跑步经过每一条小路，每条路至少经过一次，最后必须再回到开始时的花坛，那么最短的跑步路程是多长？

Format

Input

输入包含多组测试数据。

每组输入的第一行为2个正整数n和m（n<=15，m<1000），n表示花坛的个数，m表示小路的个数。当n=0时，输入结束。

接下来m行，每行输入3个正整数s，e，l（1<=s,e<=n，1<=l<=5000），表示标号为s和e的花坛由一条小路相连，长度为l。任意两个花坛之间可能会由多条小路相连而且小路的长度也可能会相等。每条小路都是双向可通行的。从任何一条小路通过连接小路的花坛都可以到达其他任何一条小路。

Output

对于每组输入，输出小明满足题目要求要跑的最短路程。

Samples

4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
0

41

Limitation

1s, 1024KiB for each test case.