旅行售货员问题的近似算法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description


设计并实现上述近似算法。

Input

输入数据的第1 行有2个正整数n和e(n≤20,e≤400),n表示G 的顶点数;e是G 的边数。接下来的e 行中,每行有3 个正整数i,j,c,表示边(i,j)的费用为c。

Output

将近似最优哈密顿回路及其长度输出。第1 行是近似最优哈密顿回路的长度,第2 行是近似最优哈密顿回路。

Sample Input

7 8
1 4 5
4 2 8
2 6 3
6 5 1
5 3 3
3 7 2
7 1 9
1 5 10

Sample Output

31
1 4 2 6 5 3 7

Hint

 

Source