#include<iostream>
using namespace std;

const maxl=10000;

int n,m,a[105][105]={0};
long min_p=100000,p[105]={0},sum=0;


void prov(int st[105],int n)
{
    int i;

    sum+=a[st[n]][st[1]];
    if(min_p>sum)
    {
        min_p=sum;
        for(i=1;i<=n;i++)p[i]=st[i];
        p[0]=i-1;
    }

    sum-=a[st[n]][st[1]];
}


void circl(int v)
{
    int i,i1=1,k,n1=1,st[105]={0},pp,pr[105]={0};

    st[n1]=v;
    pr[v]=1;

    while(n1>0)
    {
        k=st[n1];pp=0;
        for(i=i1;i<=n;i++)
            if(a[k][i]>0 && pr[i]==0)
            {
                n1++;
                st[n1]=i;
                pr[i]=k;
                pp=1;
                sum+=a[st[n1-1]][st[n1]];

        if(a[v][st[n1]]>0 && n1>2)prov(st,n1);
                break;
            };

        if(pp==0){i=st[n1];i1=i+1;pr[i]=0;n1--;
        sum-=a[i][st[n1]];}else i1=1;
    }

    sum=0;
}

void vvod()
{
    int i,j,k1,k2,c;
           cin>>m;

        for(i=1;i<=m;i++)
        {
            cin>>k1>>k2>>c;
            if(a[k1][k2]!=0)a[k1][k2]=a[k2][k1]=min(a[k1][k2],c);else a[k1][k2]=a[k2][k1]=c;
        }
}

int main()
{
    int i,j,k;

    for(k=1;n!=-1;k++)
    {

        cin>>n;

        if(n==-1)break;

        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)a[i][j]=0;

        vvod();

        for(i=1;i<=n;i++)circl(i);

        if(p[0]==0)cout<<"No solution."<<endl;
        else
        {
            for(i=1;i<=p[0];i++)cout<<p[i]<<" ";
            cout<<endl;
        };

        p[0]=0;
        min_p=100000;
     }

    return 0;
}