#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;

typedef struct celula {
        int nod,cost;
        celula *next;
        }*lista;

lista graf[50005],v;
int i,j,h[50006],hp,ind[50005],dist[50005],n,m;
int inf=2000000000;

void down() {
   
   int nod=1, idx;
   
   while (2*nod<=hp) {
         
         idx=nod;
         
         if (dist[idx]>dist[h[2*nod]]) idx=2*nod;
         if (2*nod+1<=hp && dist[h[2*nod+1]]<dist[h[idx]]) idx=2*nod+1;
         
         if (idx==nod) break;
         else {
              
              swap(ind[nod],ind[idx]);
              swap(h[nod],h[idx]);
              nod=idx;
              
              }
         
         }     
     
}

void up(int nod) {
 
    int aux=ind[nod];
    
    while (aux>1 && dist[h[aux/2]]>dist[h[aux]]) {
          swap(ind[aux],ind[aux/2]);
          swap(h[aux],h[aux/2]);
          aux/=2;
          }
}


int main(void) {
    
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    
    cin>>n>>m;
    
    for (i=1; i<=m; ++i) {
        int x,y,c;
        cin>>x>>y>>c;
        v=new celula; v->nod=y; v->cost=c; v->next=graf[x]; graf[x]=v;
        }
        
    dist[1]=0;
    hp=n;
    h[1]=1;
    
    for (i=2; i<=n; ++i) {
        dist[i]=inf;
        h[i]=i;
        ind[i]=i;
        }
        
    while (hp>0) {
          int nodc=h[1];
          h[1]=h[hp];
          --hp;
          down();
          
          for (lista p=graf[nodc]; p; p=p->next)
           if (dist[nodc]+p->cost<dist[p->nod]) {
                                                dist[p->nod]=dist[nodc]+p->cost;
                                                up(p->nod);
                                                }
          
          }
          
    for (i=2; i<=n; ++i)
     if (dist[i]==inf) cout<<"0 ";
     else cout<<dist[i]<<" ";
    
    return 0;
}