描述

戈德正在为马拉松训练。他家后面是一个公园，公园里有一大堆连接水站的慢跑道。Gord 希望找到至少沿每条小径行驶一次的最短慢跑路线。

输入

Input 由多个测试用例组成。每个 case 的第一行输入包含两个正整数：n <= 15（水站的数量）和 m < 1000（小径的数量）。对于每条步道，有一行后续输入，其中包含三个正整数：前两个介于 1 和 n 之间，表示步道终点处的水站;第三个表示小径的长度，以肘为单位。任意两个车站之间可能有多条小径;每个不同的 trail 在 input 中只给出一次;每条小径都可以朝任一方向行驶。通过访问由小径连接的一系列水站，可以从任何其他小径到达任何小径。Gord 的路线可以从任何水站开始，并且必须在同一水站结束。包含 0 的单行跟在最后一个测试用例之后。

输出

对于每种情况，都应该有一行输出给出 Gord 慢跑路线的长度。

输入数据 1

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

输出数据 1

41