#include<stdio.h>
#include<stdlib.h>
int n,m,i,j,k,d[50001],l,t,p,co,w[50001],*s[50001],*v[50001],a[250005],b[250005],e[250005],q[250005],u;
int main() {
	freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
	for(k=1;k<=m;k++)
    	scanf("%d%d%d",&a[k],&b[k],&e[k]),w[a[k]]++;
	for(i=1;i<=n;w[i++]=0) {
		d[i]=50001;
		s[i]=v[i]=(int*)malloc(w[i]*sizeof(int));
	}
	for(k=1;k<=m;k++)
    	s[a[k]][w[a[k]]]=b[k],v[a[k]][w[a[k]]++]=e[k];
	for(q[u++]=1;p<u;)
    for(t=q[p++],j=0;j<w[t];j++)
    if(d[s[t][j]]>d[t]+v[t][j])
        d[s[t][j]]=d[t]+v[t][j],q[u++]=s[t][j];
	for(i=2;i<=n;i++)
    	printf("%d ",d[i]%50001);
}