#include <stdio.h>
#include <vector>
#define inf 1000000000
#define nMax 50005

using namespace std;

long d[nMax];
long q[nMax];
long poz[nMax];
long n,m,k,i,j,r;
long x,y,z;
vector <long> v[nMax],c[nMax];

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

void scufunda(long i){
     long fiu;
     while ((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]);
              swap(poz[i],poz[fiu]);
           }
           else break;
     }
}

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

long get_min(){
     swap(q[1],q[k]);
     swap(poz[1],poz[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){
           long nod_min=get_min();
           /*for (i=1;i<=k;i++)
               printf("%ld ",q[i]);
           printf("\n");
           for (i=1;i<=k;i++)
               printf("%ld ",d[q[i]]);
           printf("\n\n");
           */
           //if (d[nod_min]==inf)break;
           for (i=0;i<v[nod_min].size();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,&y,&z);
        v[x].push_back(y);
        c[x].push_back(z);
    }
    
    dijkstra();

return 0;
}