1006:爱旅游

时间限制: 2 S | 内存限制: 65536 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

今年国庆只有七天表示很伤心啊,以往都是九天的。可是这跟XUJCACMER有关系吗?当然有了,因为ZSW他是个旅游小白痴,虽然现在工作很紧张,但他有着未来的远见,他喜欢根据当前旅游点来规划一条往返路线。当然这很可能是他为毕业游做的打算。可惜他真的在这方面显得很小白。

现在他想去的景点有N(N<=50)个,为了省钱一律走陆地路线,所以有些景点之间不要想着飞机直达了。给出M (N< M < N*N-1) 条往返路,这M条路都表示着ab需要花费c (0 < c < 300) 元。起始点为1,以此排序下来最远的终点为N.

所以他希望你可以写出一个程序来帮助他找出这条路线,让他花最少的钱走最远的路,当然就不一定非要走遍所有景点了。最后输出这条路的往返路线和总往返花费。

输入

第一行输入两个数据 NM 分别代表N个景点,M条路

后面M行有三个参数a,b,c 分别代表 a点到b点需要花费c

多组测试数据!

输出

输出往返路线和总花费

样例输入

4 7

1 2 1

1 3 1

2 4 8

3 4 2

4 1 8

4 3 1

3 1 1

样例输出

1 3 4 3 1 5

HINT

注意输出格式,看清楚。

来源
XUJC OJ