1965_John的自驾游线路

John最喜欢自驾游了。自从退休后，John就一直在筹备一次环游世界的自驾游。

John生活的世界的国家的城市网络构成有如下特点：

1. 每个国家有且只有一个城市与外国的城市连通

2. 每个国家由若干个省/邦组成。任意两个省/邦之间最多只有一条路线连通。

3. 每个省/邦有k个城市（ 0 < k ≤ 16 ），一个省/邦内的任意两座城市之间至少有两条不同的行走路线，除非这个省/帮的城市数小于3

John希望规划一条最短的路线，经过每个城市至少一次，最后回到出发点。

多测试用例。每个测试用例：

第一行是两个正整数 n 和 e （ 1< n < 500 ， 1< e < 120000 ），n表示全世界城市的总数（编号是0～n-1），e表示连接城市的道路的总数。

接下来e行，每行3个整数 u ，v 和 w，（ 0 ≤ u, v < n ，0 < w < 50 ）表示城市u和城市v之间有一条双向道路，长度为 w 。

John所在的城市编号是0 。

每个测试用例输出两行结果：

第一行：周游世界的最短路线的长度

第二行：该路线的城市顶点序列。

14 22
0 1 3
1 2 4
2 3 7
3 4 3
4 5 50
5 6 5
6 2 5
2 4 5
2 5 4
3 6 9
3 5 8
4 6 3
1 7 9
7 8 5
8 9 3
7 10 7
10 11 4
11 12 9
12 13 4
13 10 7
10 12 3
13 11 7

102
0 1 2 5 6 4 3 2 1 7 8 9 8 7 10 12 13 11 10 7 1 0

样例对应的图

实线圈包围的是一个国家，虚线包围的是一个省/邦，带标号的小圈表示城市，线段表示城市之间的道路长度。