#include <stdio.h>

#define fr(i,a,b) for(int i=a;i<=b;++i)
const int MAXN = 50001;
const int veg = 1 << 30;

struct graf
{
    int csp, ut;
    graf *kov;
};

int n,m;
graf *t[MAXN];
int d[MAXN],h[MAXN],poz[MAXN],k;

void add(int a, int b, int c)
{
    graf *q = new graf;
    q->csp = b;
    q->ut = c;
    q->kov = t[a];
    t[a] = q;
}

void be()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    int a,b,c;
    fr(i,1,m)
    {
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
    }
}

void csere(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(int a)
{
    int ap;
    while(a>1)
    {
        ap=a>>1;
        if(d[h[ap]]>d[h[a]])
        {
            poz[h[a]]=ap;
            poz[h[ap]]=a;
            csere(ap,a);
            a=ap;
        }
        else
            a = 1;
    }
}

void downheap(int a)
{
    int f;
    while(a<=k)
    {
        f=a;
        if((a<<1)<=k)
        {
            f=a<<1;
            if(f+1<=k)
                if(d[h[f+1]]<d[h[f]])
                    ++f;
        }
        else
            return;

        if (d[h[a]]>d[h[f]])
        {
            poz[h[a]]=f;
            poz[h[f]]=a;
            csere(a,f);
            a=f;
        }
        else
            return;
    }
}

void dijkstra()
{
    fr(i,2,n) d[i]=veg,poz[i]=-1;
    poz[1] = 1;
    h[++k] = 1;
    while(k)
    {
        int min=h[1];
        csere(1,k);
        poz[h[1]]=1;
        --k;
        downheap(1);
        graf *q=t[min];

        while(q)
        {
            if(d[q->csp]>d[min]+q->ut)
            {
                d[q->csp]=d[min]+q->ut;
                if(poz[q->csp]!=-1)
                    upheap(poz[q->csp]);
                else
                {
                    h[++k]=q->csp;
                    poz[h[k]]=k;
                    upheap(k);
                }
            }
            q=q->kov;
        }
    }
}

int main()
{
    be();
    dijkstra();
    fr(i,2,n) printf("%d ",d[i]==veg?0:d[i]);
    printf("\n");
    return 0;
}