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