#include <fstream>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
typedef struct celula {
                       long nod;
                       long cost;
                       celula* next;
                       }*lista;
const long INF=999999999;

void coboara(long nod,long D[],long H[],long lungime)
{
 long fiu(INF),aux;
 do {
     fiu=0;
     if (nod*2<=lungime) { 
                          fiu=nod*2;
                          if  ((nod*2<lungime) && (D[H[nod*2+1]]<D[H[nod*2]])) fiu=nod*2+1;
                          if  (D[H[fiu]]>=D[H[nod]]) fiu=0;
                         }
     if (fiu) {
               swap(H[nod],H[fiu]);
               nod=fiu;
              }
     }
 while (fiu);            
}
           
long n,i,a,b,c,v,k,aux1,m,lungime(1),aux,H[50013],D[50013];
lista lda[50013],r;
int main()
{
  cin>>n>>m;
  aux1=n;
  for (i=1;i<=m;++i){
                     cin>>a>>b>>c;
                     r=new celula;
                     r->nod=b;
                     r->cost=c;
                     r->next=lda[a];
                     lda[a]=r;
                     }
  for (i=2;i<=n;++i) D[i]=INF;
  H[1]=1;
  while (lungime){
                 v=H[1];
                 r=lda[v];
                 H[1]=H[lungime];
                 --lungime;
                 coboara(1,D,H,lungime);
                 while(r){
                          if (D[v]+r->cost < D[r->nod]) {
                                                          D[r->nod]=D[v]+r->cost;
                                                          H[++lungime]=r->nod;
                                                          k=lungime;
                                                          while ((k>1) && (D[H[k]]<D[H[k/2]])){
                                                                                               swap(H[k],H[k/2]);
                                                                                               k/=2;
                                                                                               }
                                                          }
                          r=r->next;
                          }
                  } 
for (i=2;i<=aux1;++i)
                   if (D[i]==INF) cout<<0<<" ";
                             else cout<<D[i]<<" "; 
return 0;
}