Acmer先生决定访问n座城市。他可以空降到任意城市，然后开始访问，要求访问到所有城市，任何一个城市访问的次数不少于1次，不多于2次。n座城市间有m条道路，每条道路都有路费。求Acmer先生完成旅行需要花费的最小费用。
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
动规专题