1494：【例 1】Sightseeing Trip

题目描述

给定一张无向图，求图中一个至少包含 $3$ 个点的环，环上的节点不重复，并且环上的边的长度之和最小。该问题称为无向图的最小环问题。

在本题中，你需要输出最小环的具体方案（按环上的顺序输出节点）。若最小环不唯一，输出任意一个均可。若无解，输出 No solution.。

输入格式

第一行两个正整数 $n, m$ 表示点数和边数。

接下来 $m$ 行，每行三个正整数 $x, y, z$，表示节点 $x$ 和 $y$ 之间有一条长度为 $z$ 的边。

输出格式

输出一行，包含一个最小环的方案，按环上顺序输出节点（用空格分隔）。若最小环不唯一，输出任意一个均可。若无解，输出 No solution.。

样例

样例输入 #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

样例解释 #1

图中存在多个环，例如：

• 环 1 → 3 → 1（边权为 300+10=310，但重复节点 1 和 3，不合法）
• 环 1 → 2 → 3 → 1（边权 16+100+10=126）
• 环 1 → 3 → 5 → 2 → 1（边权 10+20+15+16=61）
• 环 1 → 3 → 5 → 2 → 1 是最小的合法环（至少 3 个不同节点），总权值为 61，输出为 1 3 5 2（起点和终点在环中是同一个节点，输出时省略最后一个重复的起点）。

注意：环的输出顺序要求是环上节点的顺序，可以从任意节点开始，顺时针或逆时针方向均可。

数据范围

• $1 \le n \le 100$
• 边权 $z$ 为正整数，具体范围未给出，但应在合理范围内
• 图中可能有重边，但自环无效（因为要求至少 3 个不同节点）

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB
• Special Judge：本题使用 Special Judge 进行评测，允许输出任意一个最小环方案。