#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
FILE *f1=fopen("dijkstra.in","r");
FILE *f2=fopen("dijkstra.out","w");
int n,m,d[50001],i;
class comp{
public:
    bool operator() (const int &a,const int &b){
       return d[a]>d[b];
    }
};
priority_queue<int,vector<int>,comp>Q;
struct nod{
   int inf,drum;
   nod *urm;
}*L[50001];
void inseraresf(nod *&vf,int val1,int val2){
    nod *q;
    q=new nod;
    q->inf=val1;
    q->drum=val2;
    q->urm=vf;
    vf=q;
}
void citire(){
   fscanf(f1,"%d%d",&n,&m);
   int k,i,j,cost;
   for (k=1;k<=n;k++)
     L[k]=0;
   for (k=1;k<=m;k++){
      fscanf(f1,"%d%d%d",&i,&j,&cost);
      inseraresf(L[i],j,cost);
   }
   fclose(f1);
}
void dijkstra(int r){
    nod *q;
    d[r]=0;
    Q.push(r);
    int x;
    while(!Q.empty()){
       x=Q.top();
       Q.pop();
       q=L[x];
       while(q!=0){
          if (d[x]+q->drum<d[q->inf]){
              d[q->inf]=d[x]+q->drum;
              Q.push(q->inf);
          }
          q=q->urm;
       }
    }
}
int main(){
   citire();
   for (i=1;i<=n;i++)
     d[i]=10000000;
   dijkstra(1);
  for (i=2;i<=n;i++)
   if (d[i]!=10000000) fprintf(f2,"%d ",d[i]);
     else
        fprintf(f2,"0 ");
   fclose(f2);
   return 0;
}