解旅行售货员问题的近似算法approxTSP 可以进一步得到改进。由近似算法η=2的证明过程容易看出，如果将G 的最小生成树T 的边看作是G 的双重边，则回路W 就是T的一个欧拉回路。而近似最优哈密顿回路是在这条欧拉回路中删除第2 次经过的顶点得到的。如果基于T找出一条更短的欧拉回路，则可以得到一条更短的哈密顿回路。下面的算法框架就是基于这个思想来设计的。
void approxTSP (Graph G)
{
(1) 选择任一顶点r∈V；
(2) 用PRIM算法找出G 的一棵以r 为根的最小生成树T；
(3) 找出T的奇数度顶点集S；
(4) 在以S为顶点集的G的完全子图中，找出一个最小完全匹配M；
(5) 在以T和M 中所有边集组成的多重图中，找出一条欧拉回路；
(6) 将找到的欧拉回路，除根r 外第2次经过的顶点删去，得到一条哈密顿回路H；
(7) 将所得到的哈密顿回路H 作为计算结果返回。
}
上述算法是解TSP问题的 O( n³ )时间近似算法，且其性能比达到 1.5。

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

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

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