原题
开始口胡:
用类似dp的方法，对图中所有环进行分类
分类标准是环中编号最大的点
for(int k=1;k<=n;k++)
由floyd的原理可知当floyd的第一重循环执行到K时(还没开始执行K)，所有路径都是进过1到k-1号点所形成的最短距离
当进行到K时，枚举i和j，在之前的计算中包含i,j的环的距离是d[i][j]+d[j][i]，先插入K点，使式子变成w[i][k]+w[k][j]+d[j][i]取两者最小值，当把所有i,j枚举完，就能求出第K类环的最小值

#include <bits/stdc++.h>

using namespace std;
const int N = 110, INF = 1e8;
int n, m;

int d[N][N], g[N][N];
int p[N][N];//每个点是由哪个点转移过来的
int path[N], cnt; //当前环的方案 点的数量

void get_path(int i, int j) {
	if (p[i][j] == 0)
		return;
	int k = p[i][j];
	get_path(i, k); //从i走到k
	path[cnt++] = k;
	get_path(k, j); //从k走到j


}

void solve() {
	cin >> n >> m;
	int res = INF;
	memset(g, 0x3f, sizeof g);
	for (int i = 1; i <= n; i++)
		g[i][i] = 0;
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a][b] = g[b][a] = min(c, g[a][b]);
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			d[i][j] = g[i][j];
		}
	}

	for (int k = 1; k <= n; k++) {

		for (int i = 1; i < k; i++) { //求最大环
			for (int j = i + 1; j < k; j++) {
				if ((long long)d[i][j] + g[j][k] + g[k][i] < res) {
					res = d[i][j] + g[j][k] + g[k][i];
					cnt = 0;
					path[cnt++] = k;
					path[cnt++] = i;
					get_path(i, j);
					path[cnt++] = j;
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (d[i][j] > d[i][k] + d[k][j]) {
					d[i][j] = d[i][k] + d[k][j];
					p[i][j] = k; //转移的中间点
				}
			}
		}
	}
	if (res == INF) {
		cout << "No solution." << endl;
	} else {
		for (int i = 0; i < cnt; i++) {
			cout << path[i] << " ";
		}
		cout << endl;
	}

}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	solve();

}