#include<stdio.h>
const int N=50001;
struct G {
    int o,c;
    G *u;
};
G *g[N],*r;
int n,m,x,y,z,i,d[N],q[N],p,u,t,v;
int main() {
    freopen("dijkstra.in","r",stdin),freopen("dijkstra.out","w",stdout),scanf("%d%d",&n,&m);
    while(m--) {
        scanf("%d%d%d",&x,&y,&z);
        r=new G;
        r->o=y,r->c=z,r->u=g[x],g[x]=r;
    }
    for(i=2;i<=n;i++)
        d[i]=N;
    for(d[1]=0,q[u++]=1;p<u;)
    for(t=q[p++],r=g[t];r;r=r->u) {
        v=d[t]+r->c;
        if(d[r->o]>v)
            d[r->o]=v,q[u++]=r->o;
    }
    for(i=2;i<=n;i++)
        printf("%d ",d[i]%50001);
}