#include <stdio.h>
#define inf 2000000000
#define nMax 50005
#define mMax 250005

using namespace std;

long d[nMax];
long q[nMax];
long poz[nMax];
long n,m,k,i,j,r;
long nod_min;
long x[mMax],y[mMax],z[mMax],G[nMax];
long *v[nMax],*c[nMax];

void swap(long &a,long &b){
     a=a^b;
     b=b^a;
     a=a^b;
}

void scufunda(long i){
     long fiu;
     while ((long)(i<<1)<=k){
           fiu=i<<1;
           if ((long)(fiu|1)<=n)
              if (d[q[fiu|1]]<d[q[fiu]])fiu|=1;
           if (d[q[fiu]]<d[q[i]]){
              swap(q[i],q[fiu]);
              poz[q[i]]=i;
              poz[q[fiu]]=fiu;
              i=fiu;
           }
           else break;
     }
}

void ridica(long i){
     long val=q[i];
     while (i>1 && d[q[i]]<d[q[i>>1]]){
           q[i]=q[i>>1];
           poz[q[i]]=i;
           i>>=1;
     }      
     q[i]=val;
     poz[q[i]]=i;
}

long get_min(){
     swap(q[1],q[k]);
     poz[q[1]]=1;
     poz[q[k]]=k;
     k--;
     scufunda(1);
     return q[k+1];
}

void output(){
     for (i=1;i<=n;i++)
         if (i!=r)
            if (d[i]==inf)printf("0 ");
            else printf("%ld ",d[i]);
}

void dijkstra(){
     //initializare
     for (i=1;i<=n;i++){
         poz[i]=q[i]=i;
         d[i]=inf;
     }
     d[r]=0;
     k=n;
     while (k){
           nod_min=get_min();
           for (i=1;i<=G[nod_min];i++)
               if (d[v[nod_min][i]]>d[nod_min]+c[nod_min][i]){
                  d[v[nod_min][i]]=d[nod_min]+c[nod_min][i];
                  ridica(poz[v[nod_min][i]]);
               }
     }
     output();
}

int main(){
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    
    scanf("%ld %ld",&n,&m);
    r=1;//nod sursa
    
    for (i=1;i<=m;i++){
        scanf("%ld %ld %ld",&x[i],&y[i],&z[i]);
        G[x[i]]++;
    }
    for (i=1;i<=n;i++){
        v[i]=new long [G[i]+1];
        c[i]=new long [G[i]+1];
        G[i]=0;
    }
    for (i=1;i<=m;i++){
        v[x[i]][++G[x[i]]]=y[i];
        c[x[i]][G[x[i]]]=z[i];
    }
    
    dijkstra();

return 0;
}