#include <stdio.h>  
#include <string.h>  
   
#define Inf 0x3f3f3f3f  
#define Nmax 50001  



   
int x[5*Nmax],y[5*Nmax],c[5*Nmax];  
int d[Nmax];  
int n,m;  
  
int main()  
{  
  int i,j,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], &c[i]);  
      if (x[i]==1)  
	d[y[i]]=c[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]]+c[i])  
	    d[y[i]]=d[x[i]]+c[i],  
	      ok=0;  
     }  
  
  for (i=2;i<=n;++i)  
    if (d[i]!=Inf) printf("%d ", d[i]);  
	   else printf("%d ", !ok);  
  return 0;  
}