说明

终于有一个盼望已久的假期！立马拿出地图，标出最想去的n个景点，以及两个景点之间的距离$d_{ij}$，为了节省时间，我们希望在最短的时间内看遍所有的景点，而且同一个景点只经过一次。怎么计划行程，才能在最短的时间内不重复地旅游完所有景点回到家呢？

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入景点数n和景点之间的边数m（1<=n<=50，1<=m<=2500）。

接下来有m行，每行输入3个数，代表两个景点序号u、v及两景点之间的距离w（1<=u,v <=50, 1<=w <=100）。

输出格式

对于每一组输入，输出满足条件的最短距离。

每组的输出占一行。

样例

2
5 9
1 2 3
1 4 8
1 5 9
2 3 3
2 4 10
2 5 5
3 4 4
3 5 3
4 5 20
4 6
1 2 10
1 3 12
1 4 4
2 3 5
2 4 8
3 4 6

23
25

来源

《趣学算法》6.3节