3046 - 旅行
时间限制 : 1 秒
内存限制 : 128 MB
Acmer先生决定访问n座城市。他可以空降到任意城市，然后开始访问，要求访问到所有城市，任何一个城市访问的次数不少于1次，不多于2次。n座城市间有m条道路，每条道路都有路费。求Acmer先生完成旅行需要花费的最小费用。
输入
第一行是n，m，1 ≤ n≤ 10。后面有m行，有3个整数a、b、c（1≤a,b≤n），表示城市a和b之间的路费是c。
输出
最少花费，如果不能完成旅行，则输出-1。
样例
输入
2 1 1 2 100 3 2 1 2 40 2 3 50 3 3 1 2 3 1 3 4 2 3 10
输出
100 90 7
来源
动规专题