I think my code is right.
I use floyd.


/* ural1004 */

#include<iostream>
#include<string.h>
using namespace std;

const long big=100000000;
const int maxn=110;

long m,n,ai,aj,ak,ans;
long path[maxn],dist[maxn];
long map[maxn][maxn];


void floyd()
{
    long k,i,j;
    long way[maxn][maxn];
    ans=big;
    memmove(way,map,sizeof(map));
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(way[i][j]>way[i][k]+way[k][j]) way[i][j]=way[i][k]+way[k][j];
        for(i=1;i<=k-1;i++)
            for(j=1;j<=i-1;j++)
                if(map[i][k]<big && map[k][j]<big && way[i][j]<big)
                    if(way[i][j]+map[i][k]+map[k][j]<ans)
                    {
                        ans=way[i][j]+map[i][k]+map[k][j];
                        ai=i;
                        aj=j;
                        ak=k;
                    }
    }
}


void dijkstra()
{
    long i,j,k,min;
    bool check[maxn];
    if(ans==big) return;
    for(i=1;i<=n;i++) dist[i]=big;
    dist[ai]=0;
    memset(check,false,sizeof(check));
    memset(path,0,sizeof(path));
    for(i=1;i<=n-1;i++)
    {
        min=big;
        for(j=1;j<=n;j++)
            if(dist[j]<min && !check[j])
            {
                min=dist[j];
                k=j;
            }
        check[k]=true;
        if(k==aj) break;
        for(j=1;j<=n;j++)
            if(!check[j] && j!=ak && dist[j]>min+map[k][j])
            {
                dist[j]=min+map[k][j];
                path[j]=k;
            }
    }
}

void out()
{
    if(ans==big)
    {
        cout<<"No solution."<<endl;
        return;
    }
    while(aj!=0)
    {
        cout<<aj<<" ";
        aj=path[aj];
    }
    cout<<ak<<endl;
}



int main()
{
    long i,j,x,y,z;
    cin>>n;
    while(n!=-1)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) map[i][j]=big;
        cin>>m;
        for(i=1;i<=m;i++)
        {
            cin>>x>>y>>z;
            if(map[x][y]>z)
            {
                map[x][y]=z;
                map[y][x]=z;
            }
        }
        floyd();
        dijkstra();
        out();
        cin>>n;
    }
    return 0;
}