#include <stdio.h>

struct muchie{
    int i;
    int j;
    int c;
};

int n,d[50005],x[50005],y[50005],m,nv[50005],lv[250005],dmin[50005];
muchie mx[250005];


//x[i] - vf. caruia apartine d[i] in heap
//y[j] - locul in d corespunzator vf. j
// x[y[j]]=i   y[x[i]]=i


void schimba(int &a,int &b)
{
    int aux;
    aux=a; a=b; b=aux;
}


int vecin(int i,int k)
{

    return mx[k].j;
}

void swim(int k,int m,int *a,int *x,int *y)
{
    while(k>1 && a[k]<a[k/2])
    {
        schimba(a[k],a[k/2]);
        y[x[k]]=k/2;y[x[k/2]]=k;
        schimba(x[k],x[k/2]);
        k=k/2;
    }
}

void sink(int k,int m,int *a,int *x,int *y)
{
    int i=2*k;
    while(i<=m)
    {
        if(i<m && a[i+1]<a[i])
            i++;
        if(a[i]<a[k])
        {
            schimba(a[k],a[i]);
            y[x[k]]=i,y[x[i]]=k;
            schimba(x[k],x[i]);
            k=k/2;
        }
        else
            break;
        k=i;i=2*k;
    }
}


int sterge(int k,int m,int *a,int *x,int *y)
{
    int crt=x[k];

    a[k]=a[m];x[k]=x[m];
    y[x[k]]=k;
    if(k>1 && a[k]<a[k/2])
        swim(k,m,a,x,y);
    else
        sink(k,m,a,x,y);
   return crt;
}

void actual(int k,int m,int *a,int *x,int *y)
{
    if(k>1 && a[k]<a[k/2])
        swim(k,m,a,x,y);
    else
        sink(k,m,a,x,y);
}

int main()
{
    int i,j,k,c,crt,crtv,dcrt;
    FILE *f,*g;

    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");

    fscanf(f,"%d%d",&n,&m);


    for (k=1;k<=m;k++)
    {
        fscanf(f,"%d%d%d",&i,&j,&c);
        nv[i]++;
        mx[k].i=i;mx[k].j=j;mx[k].c=c;
    }
    for(i=2;i<=n;i++)
        nv[i]+=nv[i-1];
    for(k=1;k<=m;k++)
    {
        i=mx[k].i;
        lv[nv[i]--]=k;
    }
    nv[n+1]=m;

    for(i=1;i<=n;i++)
    {
        d[i]=1<<30;x[i]=i;y[i]=i;dmin[i]=-1;
    }
    d[1]=0;
    for(i=1;i<n;i++)
    {
        dmin[x[1]]=d[1];
        crt=x[1];dcrt=d[1];
        sterge(1,n-i+1,d,x,y);
        for(j=nv[crt]+1;j<=nv[crt+1];j++)
        {
           k=lv[j];crtv=vecin(crt,k);
           if(dmin[crtv]<0 && d[y[crtv]]>dcrt+mx[k].c)
            {
                d[y[crtv]]=dcrt+mx[k].c;
                actual(y[crtv],n-i,d,x,y);
           }
        }
    }
    dmin[x[1]]=d[1];
    for(i=2;i<=n;i++)
        if(dmin[i]!=1<<30)
            fprintf(g,"%d ",dmin[i]);
        else
            fprintf(g,"0 ");

}