1006:爱旅游

今年国庆只有七天表示很伤心啊，以往都是九天的。可是这跟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

注意输出格式，看清楚。