描述

在桑给巴尔岛的阿德尔顿镇有一家旅行社。除了许多其他旅游项目外，这家旅行社决定为客户提供在镇上观光的服务。为了从这个旅游项目中尽可能多地盈利，旅行社做出了一个明智的决定：必须找到一条起点和终点在同一地点的最短路线。你的任务是编写一个程序来找到这样的一条路线。

在这个镇上有$N$个交叉点，编号从$1$到$N$，还有$M$条双向道路，编号从$1$到$M$。两个交叉点之间可能有多条道路相连，但没有道路会连接一个交叉点和它自身。每条观光路线是一个道路编号序列$y_1, \ldots, y_k$ ，其中$k>2$。道路$y_i$（$1 \leq i \leq k-1$）连接交叉点$x_i$和$x_{i+1}$，道路$y_k$连接交叉点$x_k$和$x_1$。所有的数字$x_1, \ldots, x_k$都应该是不同的。观光路线的长度是这条观光路线上所有道路长度的总和，即$L(y_1)+L(y_2)+\ldots+L(y_k)$ ，其中$L(y_i)$是道路$y_i$（$1 \leq i \leq k$）的长度。你的程序必须找到这样一条长度最短的观光路线，或者指明这是不可能的，因为镇上不存在这样的观光路线。

输入

输入的第一行包含两个正整数：交叉点的数量$N \leq 100$和道路的数量$M \leq 10000$。

接下来的$M$行中的每一行描述一条道路。每行包含$3$个正整数：它的第一个交叉点的编号、第二个交叉点的编号以及这条道路的长度（一个小于$500$的正整数）。

输出

输出只有一行。如果不存在任何观光路线，这一行包含字符串“$No$ $solution.$”（无解），否则这一行包含最短观光路线上所有交叉点的编号，按照经过这些交叉点的顺序排列（即我们对观光路线的定义中的数字$x_1$到$x_k$ ），各个编号之间用单个空格分隔。如果有多个长度最短的观光路线，你可以输出其中任意一条。

输入数据 1

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

输出数据 1

1 3 5 2

来源

CEOI 1999