Floyd循坏k次，求的是i和j两点之间（不包括i和j）所经过的点最大编号是k的最短路
对于求题目说的环，可以分成k类，即环上最大的点是k
用g表示原来的图，dis表示最短路
在求Floyd时，对于第k类，如果有dis[i][j]+g[i][k]+g[k][j]小于当前最小值(i,j均小于k)
说明i到j是当前的最小环

import java.io.*;
import java.util.*;

public class Main{
    static int N = 110;
    static int[][] g = new int[N][N],dis = new int[N][N];
    static int[] path = new int[N];
    static int[][] pos = new int[N][N];
    static int n,m,cnt = 0,INF = 0x3f3f3f3f;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 0;i<N;i++)
            Arrays.fill(g[i],INF);
        for(int i = 0;i<N;i++)
            g[i][i] = 0;

        for(int i = 0;i<m;i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            g[a][b] = g[b][a] = Math.min(g[a][b],c);
        }
        for(int i = 0;i<N;i++)
            for(int j = 0;j<N;j++)
                dis[i][j] = g[i][j];

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

            for(int i = 1;i<k;i++)
                for(int j = i+1;j<k;j++)
                    if((long)dis[i][j]+g[i][k]+g[k][j]<res){
                        res = dis[i][j]+g[i][k]+g[k][j];
                        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(dis[i][j]>dis[i][k]+dis[k][j]){
                        dis[i][j] = dis[i][k]+dis[k][j];
                        pos[i][j] = k;
                    }
        }
        if(res == INF) System.out.println("No solution.");
        else{
            for(int i = 0;i<cnt;i++)
                System.out.print(path[i]+" ");
        }
    }
    public static void get_path(int i,int j){
        if(pos[i][j] == 0) return;
        int k = pos[i][j];
        get_path(i,k);
        path[cnt++] = k;
        get_path(k,j);
    }
}