#include<stdio.h>

using namespace std;

struct nod{
  long int info;
  long int cost;
  nod* urm;
} *v[50001];

long int d[50001], q[50001];

long int n, m, hsize;

FILE *fin,*fout;

void initus(){
  long int i;
  for(i=1;i<=n;i++)
    d[i]=1001;
  d[1]=0;
}

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

void heapify(long int i){
  long int min=i;
  if((i<<1)<=hsize) if( d [ q[min] ] > d [ q [ (i<<1) ] ] )       min=(i<<1);
  if((i<<1)+1<=hsize) if( d [ q[min] ] > d [ q [ (i<<1)+1 ] ] )       min=(i<<1)+1;
  intersch( q[min], q[i] );
  if( min!=i ) heapify( min );
}

void buildheap(){
  long int i;
  for(i=1;i<=n;i++)
    q[i]=i;
  hsize=n;
  for(i=n/2;i>0;i--)
    heapify(i) ;
}

long int extrmin(){
   long int mi=q[1];
   intersch(q[1], q[hsize]);
   hsize--;
   heapify(1);
   return mi;
}
void relax(long int n1, long int n2, long int c){
   if(d[n2]>d[n1]+c)
     d[n2]=d[n1]+c;
}

void dijkstra(){
  initus();
  buildheap();
  long int u;
  nod*p;
  while(hsize){
     u=extrmin();
     p=v[u];
     while(p){
       relax(u, p->info, p->cost );
       p=p->urm;
     }
  }
}

void add(nod *&vf, long int x, long int y){
  nod* p=new nod;
  p->info=x;
  p->cost=y;
  p->urm=vf;
  vf=p;
}

int main(){
  long int i, x, y, z;
  fin=fopen("dijkstra.in", "rt");
  fscanf(fin, "%d%d", &n, &m);
  for(i=0;i<m;i++){
    fscanf(fin, "%d%d%d", &x, &y, &z);
    add(v[x],y,z);
  }
  fclose(fin);
  dijkstra();
  fout=fopen("dijkstra.out", "wt");
  for(i=2;i<=n;i++){
    if(d[i]==1001)  d[i]=0;
    fprintf(fout, "%d ", d[i]);
  }
  fprintf(fout, "\n");
  fclose(fout);
  return 0;
}