#include <iostream>
#include <fstream>
#define inf 9999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, dist, x, y, t[50001], d[50001], s[50001], k;
struct nod
{
    nod *next;
    int info, dist;
}*p[50001], *u[50001];
void adauga(nod *&p, nod *&u, int x, int dist)
{
    nod *c = new nod;
    c->info=x;
    c->dist=dist;
    c->next=0;
    if(p==0)
    {
        p=c;
        u=c;
    }
    else
    {
        u->next=c;
        u=c;
    }
}
int cautak()
{
    int dmin=inf, poz=0;
    for(int i=1; i<=n; i++)
    {
        if(dmin>d[i]&&s[i]==0)
        {
            dmin=d[i];
            poz=i;
        }
    }
    return poz;
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        d[i]=inf;
    }
    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>dist;
        adauga(p[x], u[x], y, dist);
    }
    for(nod *q=p[1]; q!=NULL; q=q->next)
    {
        d[q->info]=q->dist;
        t[q->info]=1;
    }
    s[1]=1;
    k=cautak();
    while(k)
    {
        cout<<k<<' ';
        for(int i=1; i<=n; i++)
        {
            for(nod *q=p[k]; q!=NULL; q=q->next)
            {
                if(q->info==i)
                    if(d[i]>d[k]+q->dist)
                    {
                        d[i]=d[k]+q->dist;
                        t[i]=k;
                    }
            }
        }
        s[k]=1;
        k=cautak();
    }
    for(int i=2; i<=n; i++)
    {
        if(d[i]!=inf)
        fout<<d[i]<<' ';
        else fout<<"0 ";
    }
    fin.close();
    fout.close();
    return 0;
}