问题描述
经过多年的努力，Victor终于考到了飞行驾照。为了庆祝这件事，他决定给自己买一架飞机然后环游世界。他会驾驶一架飞机沿着规定的航线飞行。在地球上一共有$n$个国家，编号从$1$到$n$，各个国家之间通过$m$条双向航线连接，第$i$条航线连接第$u_i$个国家与第$v_i$个国家，通过这条航线需要消耗$w_i$升油，且从$1$号国家可以直接或间接到达$2$到$n$中任意一个国家。
Victor一开始位于$1$号国家，他想知道从$1$号国家出发，经过各个国家至少一次并最后回到$1$号国家消耗的总油量的最小值是多少。
输入描述
第一行包含一个整数$T$，表示测试数据的组数。
每组测试数据的第一行有两个整数$n$和$m$，表示国家的个数和航线的条数。
接下来$m$行，每行三个整数$u_i$, $v_i$, $w_i$，描述一条航线。
$1\leq T\leq 20$。
$1\leq n\leq 16$。
$1\leq m\leq 100000$。
$1\leq w_i\leq 100$。
$1\leq u_i, v_i \leq n$。
输出描述
每组测试数据输出一行一个整数，即消耗的总油量的最小值。
输入样例
1
3 2
1 2 2
1 3 3
输出样例
10
