P2029 [第三章例题2.1]sightseeing trip
描述
在桑给巴尔岛的阿德尔顿镇有一家旅行社。除了许多其他景点外，它还决定为其客户提供观光服务。为了从这个景点尽可能多地赚钱，该机构接受了一个精明的决定：有必要找到在同一个地方开始和结束的最短路线。你的任务是编写一个找到这样一条路线的程序。
在镇上有N个交叉点，从1到N编号，M个双向道路从1到M编号。两个交叉点可以通过多条道路连接，但没有道路连接交叉点与自身。每个观光路线是一系列道路编号y_1，...，y_k，k> 2。道路y_i（1 <= i <= k-1）连接交叉点x_i和x_ {i + 1}，道路y_k连接交叉点x_k和x_1。所有数字x_1，...，x_k应该不同。观光路线的长度是观光路线上所有道路的长度之和，即L（y_1）+ L（y_2）+ ... + L （y_k）其中L（y_i）是道路y_i的长度（1 <= i <= k）。你的计划必须找到这样一条观光路线，其长度很短，或指定不可能，因为镇上没有观光路线。
在镇上有N个交叉点，从1到N编号，M个双向道路从1到M编号。两个交叉点可以通过多条道路连接，但没有道路连接交叉点与自身。每个观光路线是一系列道路编号y_1，...，y_k，k> 2。道路y_i（1 <= i <= k-1）连接交叉点x_i和x_ {i + 1}，道路y_k连接交叉点x_k和x_1。所有数字x_1，...，x_k应该不同。观光路线的长度是观光路线上所有道路的长度之和，即L（y_1）+ L（y_2）+ ... + L （y_k）其中L（y_i）是道路y_i的长度（1 <= i <= k）。你的计划必须找到这样一条观光路线，其长度很短，或指定不可能，因为镇上没有观光路线。
输入
第一行输入包含两个正整数：交叉点的数量N <= 100并且道路的数量M <= 10000。接下来的M行中的每一行描述一条道路。它包含3个正整数：第一个交叉点的数量，第二个交叉点的数量和道路的长度（小于500的正整数）。
输出
输出中只有一行。它包含一个字符串'No solution'。如果没有任何观光路线，或者它包含最短观光路线上所有过境点的数量，按顺序通过它们（即我们对观光路线的定义中的数字x_1到x_k），由单个分隔空间。如果有多个最小长度的观光路线，您可以输出其中任何一个。
样例输入
5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20
样例输出
1 3 5 2
