#include <cstdio>
using namespace std;
#define NMAX 50001
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");
struct graf {
graf *urm;
int x,c;
} *G[NMAX];
int m,n,C[NMAX],Q[10*NMAX],k,viz[NMAX];
void add(graf *&g,int x,int c)
 {
 graf *p=new graf;
 p->x=x;
 p->c=c;
 p->urm=g;
 g=p;
 }
int main()
 {
 int x,y,c,i;
 fscanf(f,"%d %d",&n,&m);
 for(int i=1;i<=m;i++)
  {
  fscanf(f,"%d %d %d",&x,&y,&c);
  add(G[x],y,c);
  }
 for(i=2;i<=n;i++)
  C[i]=1<<18;
 Q[0]=1;
 for(i=0;i<=k;i++)
  {
  x=Q[i];
  viz[x]=false;
  for(graf *p=G[x];p!=NULL;p=p->urm)
   {
   if(C[p->x]>C[x]+p->c)
    {
	C[p->x]=C[x]+p->c;
	if(!viz[p->x])
	 {
	 viz[p->x]=true;
	 Q[++k]=p->x;
	 }
    }
   }
  }
 for(int i=2;i<=n;i++)
  fprintf(g,"%d ",(C[i]!=1<<18)?(C[i]):(0));
 return 0;
 }