描述 |
---|
今年国庆只有七天表示很伤心啊,以往都是九天的。可是这跟XUJCACMER有关系吗?当然有了,因为ZSW他是个旅游小白痴,虽然现在工作很紧张,但他有着未来的远见,他喜欢根据当前旅游点来规划一条往返路线。当然这很可能是他为毕业游做的打算。可惜他真的在这方面显得很小白。 现在他想去的景点有N(N<=50)个,为了省钱一律走陆地路线,所以有些景点之间不要想着飞机直达了。给出M (N< M < N*(N-1)) 条往返路,这M条路都表示着a到b需要花费c (0 < c < 300) 元。起始点为1,以此排序下来最远的终点为N.
所以他希望你可以写出一个程序来帮助他找出这条路线,让他花最少的钱走最远的路,当然就不一定非要走遍所有景点了。最后输出这条路的往返路线和总往返花费。 |
输入 |
第一行输入两个数据 N,M 分别代表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 |