#include <stdio.h>

#define IN "dijkstra.in"
#define OUT "dijkstra.out"
#define INF 1<<30

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

struct muchie
{
 long sursa;
 long dest;
 long dist;
}e[250005];

long d[50005];
long n,m;

int main()
{
 long i,j,x,y;
 long c;

 fscanf(fin,"%ld %ld",&n,&m);

 for(i=1;i<=m;i++)
 {
  fscanf(fin,"%ld %ld %ld",&x,&y,&c);
  e[i].sursa=x;
  e[i].dest=y;
  e[i].dist=c;
  
  if(x==1)
   d[y]=c;
 }
 fclose(fin);

 for(i=2;i<=n;i++)
  if(d[i]==0)
   d[i]=INF;
   
 for(c=1;c==1;)
 {
  c=0;
  
  for(i=1;i<=m;i++)
   if(d[e[i].dest]>d[e[i].sursa]+e[i].dist)
   {
    d[e[i].dest]=d[e[i].sursa]+e[i].dist;
    c=1;
   }
 }

 for(i=2;i<=n;i++)
  if(d[i]==INF)
   fprintf(fout,"0 ");
  else
   fprintf(fout,"%ld ",d[i]);

 fclose(fout);
return 0;
}