#include<cstdio>
#define N 50001
int n,m,i,j,k,d[N],l,t,p,co,w[N],*s[N],*v[N],a[5*N],b[5*N],e[5*N],q[5*N],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]=N;
      s[i]=new int[w[i]];
      v[i]=new int[w[i]];}
for(k=1;k<=m;k++)
      s[a[k]][w[a[k]]]=b[k],v[a[k]][w[a[k]]++]=e[k];     
d[1]=0,q[u++]=1;
while(p<u)
      {t=q[p++];
      for(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]%N);
return 0;}