#include <stdio.h>    
#include <string.h>    
     
#define Inf 0x3f3f3f3f    
#define Nmax 50004    
    
int x[5*Nmax],y[5*Nmax],w[5*Nmax];    
int d[Nmax];    
int n,m;    
  
int main()    
{    
  int i,ok;    
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);
    
  scanf("%d %d\n", &n,&m);    
    
  memset(d,0,sizeof(d));    
     
  for (i=1;i<=m;++i)    
    {    
      scanf("%d %d %d\n", &x[i], &y[i], &w[i]);    
      if (x[i]==1)    
		d[y[i]]=w[i];    
    }    
      
  for (i=2;i<=n;++i)    
    if (d[i]==0)    
      d[i]=Inf;     
      
  ok=0;    
  while(!ok)    
    {    
    ok=1;      
    for (i=1;i<=m;++i)    
      if (d[y[i]]>d[x[i]]+w[i])    
        d[y[i]]=d[x[i]]+w[i],    
          ok=0;    
	}    
  for (i=2;i<=n;++i)    
    if (d[i]!=Inf) printf("%d ", d[i]);    
       else printf("0 ");//printf("Drumul e infinit");//printf("%d ", !ok);    
  return 0;    
}