Description

在桑给巴尔岛的阿德尔顿镇，有一家旅行社。除了许多其他景点外，这家旅行社决定为其客户提供该镇的观光旅游。为了从这个项目中获得尽可能多的收益，旅行社做出了一个精明的决定：需要找到一条始于同一地点并结束于同一地点的最短路线。你的任务是编写一个程序来找到这样的一条路线。

在该镇有 $N$ 个编号为 1 到 $N$ 的交叉点，以及 $M$ 条编号为 1 到 $M$ 的双向道路。两个交叉点可以通过多条道路连接，但没有道路连接同一个交叉点。每条观光路线是由道路编号 $y_1$, ..., $y_k$ 组成的序列，其中 $k > 2$。道路 $y_i (1 \le i \le 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 \le i \le k)$ 的长度。你的程序需要找到这样一条观光路线，使其长度最小，或者指明不可能找到这样的路线，因为该镇中没有任何观光路线。

Input Format

输入第一行包含两个正整数：交叉点的数量 $N \le 100$ 和道路的数量 $M \le 10000$。接下来的 $M$ 行每行描述一条道路。每行包含三个正整数：第一个交叉点的编号，第二个交叉点的编号，以及道路的长度（小于 500 的正整数）。

Output Format

输出只有一行。如果没有任何观光路线，则输出字符串 “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

4 3
1 2 10
1 3 20
1 4 30

No solution.