旅游
飘谊到了S国旅游，S国有n个城市，城市之间有许多观光道路，为了看到最多的风景，飘谊希望从某个城市出发，走完所有的观光道路，并且回到出发点。飘谊想知道他走完观光道路并回到源点的最短路径
Input
输入包含多组测试数据。
每组输入的第一行为2个正整数n和m（n<=15，m<1000），n表示城市的个数，m表示观光道路的个数。接下来m行，每行输入3个正整数u，e，l（1<=u,e<=n，1<=l<=5000），表示标号为u和e的城市由一条路相连，长度为l。任意两个城市之间可能会由多条路相连而且路的长度也可能会相等。每条路都是双向可通行的。任意两个城市是可以相互到达的。
每组输入的第一行为2个正整数n和m（n<=15，m<1000），n表示城市的个数，m表示观光道路的个数。接下来m行，每行输入3个正整数u，e，l（1<=u,e<=n，1<=l<=5000），表示标号为u和e的城市由一条路相连，长度为l。任意两个城市之间可能会由多条路相连而且路的长度也可能会相等。每条路都是双向可通行的。任意两个城市是可以相互到达的。
Output
对于每组输入，输出最短路。
Sample Input
4 5
1 2 3
2 3 4
3 4 5
1 4 10
1 3 12
Sample Output
41