#include <fstream>
#include <stdio.h>
using namespace std;
ofstream g("dijkstra.out");
FILE * stefi;
struct nod
            {
                long long inf,dis;
                nod *urm;
            };
nod *p[50003],*ultim[50003];
long long n,m,a,b,c,i,x;
long long viz[50003],l[50003];
void creare(nod *p[50003],nod *ultim[50003],long long n)
{
    for (i=1;i<=n;i++)
    {   p[i]=new nod;
        p[i]->inf=0;
        p[i]->urm=NULL;
        ultim[i]=p[i];
    }
}
void citire()
{
    nod *q;
    for (i=1;i<=m;i++)
    {
        fscanf(stefi,"%ld%ld%ld",&a,&b,&c);
        q=new nod;
        q->inf=b;
        q->dis=c;
        q->urm=NULL;
        ultim[a]->urm=q;
        ultim[a]=q;
    }
}
void sterg()
{
   nod *q;
   for (i=1;i<=n;i++)
   {
       q=p[i];
       p[i]=p[i]->urm;
       q->urm=NULL;
       delete q;
   }
}
void dijkstra()
{
    nod *q;
    long long j,minim,maxim=999999999;
    x=1;
    viz[x]=1;
    q=p[x];
    while (q)
    {
        l[q->inf]=q->dis;
        q=q->urm;
    }
    for (i=1;i<=n;i++)
        if (i!=x && !l[i]) l[i]=maxim;
    l[x]=0;
    for (i=1;i<=n-1;i++)
    {
         minim=maxim;
        for (j=1;j<=n;j++)
        {
            if (viz[j]==0 && l[j]<minim)
            {
                 minim=l[j];
                 x=j;
            }
        }
        viz[x]=1;
        q=p[x];
        while (q)
        {
            if (viz[j]==0 && l[q->inf]>l[x]+q->dis)
                l[q->inf]=l[x]+q->dis;
            q=q->urm;
        }
    }
}
int main()
{
    stefi=fopen("dijkstra.in","r");
    fscanf(stefi,"%ld%ld",&n,&m);
    creare(p,ultim,n);
    citire();
    sterg();
    dijkstra();
    for (i=2;i<=n;i++)
        g<<l[i]<<' ';
    g.close();
    return 0;
}