#include <stdio.h>
#define Nmax 50009
#define inf  0xfffff

int d[Nmax],a[5*Nmax],b[5*Nmax],c[5*Nmax],n,m,i,j,np;

int main()
{
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);

   scanf("%d%d",&n,&m);
   for (i=0;i<m;i++)
   	scanf("%d%d%d",a+i,b+i,c+i);
   int ok=1;d[1]=0;
   for (i=2;i<=n;i++)
   	d[i]=inf;np=0;
   while (ok && np<n)
   {
   	ok=0;
   	for (i=0;i<m;i++)
   	{
   		if (d[a[i]]+c[i]<d[b[i]])
   		{
           d[b[i]]=d[a[i]]+c[i];
           ok=1;
   		}
   	}
   	np++;
   }
  
  for (i=2;i<=n;i++)
  	printf("%d ",d[i]==inf ? 0:d[i]);

	return 0;
}