#include <stdio.h>
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define nmax 50000
struct nod { int info;
	     int cost;
	     nod *next;
	      };
nod  *a[nmax+1];
int d[nmax+1],viz[nmax+1],m,n,pmin,min=nmax+1;

int main()
{
 freopen(FIN,"rt",stdin);
 freopen(FOUT,"wt",stdout);

 scanf("%d%d",&n,&m);

 int i,j,k,x,y,z;
 for(i=1;i<=m;++i)
    { scanf("%d%d%d",&x,&y,&z);
      nod *p;
      p=new nod;
      p->info = y;
      p->cost = z;
      p->next= a[x];
      a[x]=p;
     }

  viz[1]=1;
  nod *p = a[1];

  for(i=2;i<=n;i++)
   d[i]= 1000;

  while (p!=NULL) { d[p->info]=p->cost;
		    p=p->next;}

  for(i=2;i<=n;++i)
  {    min = nmax;
       for(j=1;j<=n;++j)
	if(viz[j]==0)
	  if(d[j]<min) { min = d[j];
			 pmin = j;
			}
	p = a[pmin];
	while (p!=NULL)
	   { if (d[p->info] > d[pmin] + p->cost)
	      d[p->info] = d[pmin] + p->cost;
	      p=p->next;
	    }
	viz[pmin]=1;

  }


  for(i=2;i<=n;++i)
      if(d[i]!=nmax) printf("%d ",d[i]);
       else printf("0 ");


 return 0;
}