poj1734

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxx 99999999
using namespace std;
int n,m,t;
int dis[105][105],w[105][105],pre[105][105],path[105];
int floyd(){
    int i,j,k,p,x;
    x=maxx;
    for(k=1;k<=n;k++){
        for(i=1;i<k;i++)
        for(j=i+1;j<k;j++)
        if(x>dis[i][j]+w[j][k]+w[k][i]){
            x=dis[i][j]+w[j][k]+w[k][i];
            p=j;
            t=0;
            while(p!=i){                        // path      ,pre    j       
                path[t++]=p;                    
                p=pre[i][p];
            }
            path[t++]=i;
            path[t++]=k;                        //      j     i k
        }
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(dis[i][j]>(dis[i][k]+dis[k][j])){
        dis[i][j]=dis[i][k]+dis[k][j];
        pre[i][j]=pre[k][j];                    //  j pre   
        }                                       //floyd    
    }
    if(x<maxx)
    return 1;
    else
    return 0;                                   //      0
}
int main(){
    int i,j,a,b,c,temp;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            dis[i][j]=w[i][j]=maxx;
            pre[i][j]=i;                        //   pre  
        }
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            if(c<dis[a][b]){                    //     
                dis[a][b]=dis[b][a]=c;
                w[a][b]=w[b][a]=c;
            }
        }
        temp=floyd();
        if(temp){
            for(i=0;i<t;i++)
            printf("%d ",path[i]);
            printf("
");
        }
        else
        printf("No solution.
");
    }
    return 0;
}