#include<fstream.h>
#define DIM 50001

#define MAX 50000001
struct lista{int inf,cost;
	    lista *urm;
	    }*p[DIM],*q;
int n,m,x,y,z,i,j,k,d[DIM],v[DIM],min,pmin;

int main(){
  ifstream f("dijkstra.in");
  f>>n>>m;
  for (i=1;i<=n;i++)
     {p[i]=NULL;d[i]=MAX;}

  for (i=1;i<=m;i++)
   {f>>x>>y>>z;
    q=new lista;
    q->inf=y;
    q->cost=z;
    q->urm=p[x];
    p[x]=q;
/*   q=new lista;
    q->inf=x;
    q->cost=z;
    q->urm=p[y];
    p[y]=q;*/
   }
  d[1]=0;k=0;
  while (k!=n){
     min = MAX;
     for (i=1;i<=n;i++)
	if (v[i]==0&&d[i]<min){
	  min=d[i];
	  pmin=i;
	}
     if (min==MAX) break;
     v[pmin]=1;
     k++;
     q=p[pmin];
     while (q!=NULL) {
       if ((q->cost+d[pmin]<d[q->inf])) {
	 d[q->inf] = q->cost+d[pmin];
       }
       q=q->urm;
     }
  }
  f.close();

  ofstream g("dijkstra.out");
  for (i=2;i<=n;i++) {
    if (d[i]==MAX) d[i]=0;
    g<<d[i]<<" ";
  }
  g.close();
  return 0;
}