#include <iostream>
#include <fstream>
using namespace std;
ifstream f("graf.in");
int n,viz[50000],t[50000],D[50000],A[5000][5000];
void citire(int &n,int A[5000][5000])
{
    int i,j,m,x,y,c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        A[x][y]=c;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(A[i][j]==0 && i!=j)
                A[i][j]=1000000;
}
void Dijkstra(int start)
{
    viz[start]=1;
    int i,ok=0;
    for(i=1;i<=n;i++)
        D[i]=A[start][i];
    while(ok==0)
    {
        int mini=1000000,x;
        for(i=1;i<=n;i++)
            if(viz[i]==0 && D[i]<=mini)
            {
                mini=D[i];
                x=i;
            }
        if(mini==1000000)
            ok=1;
        else
        {
        viz[x]=1;
        for(i=1;i<=n;i++)
            if(viz[i]==0 && D[i]>D[x]+A[x][i])
                {
                    D[i]=D[x]+A[x][i];
                    t[i]=x;
                }
        }
    }
}
void afis(int x)
{
    if(t[x]==0)
        cout<<"1 "<<x<<" ";
    else
    {afis(t[x]);
    cout<<x<<" ";}
}
int main()
{
    citire(n,A);
    Dijkstra(1);
    int x=6;
    afis(x);
}