#include<fstream.h>
#define N 50001
#define M 250001
long n,m,i,j,k,d[N],l,t,p,co,w[N],*s[N],*v[N],a[M],b[M],e[M],q[M],u;
int main()
{ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
f>>n>>m;
for(k=1;k<=m;k++)
      f>>a[k]>>b[k]>>e[k],w[a[k]]++;
for(i=1;i<=n;w[i++]=0)     
      {d[i]=N;
      s[i]=(long*)malloc(w[i]*sizeof(long));
      v[i]=(long*)malloc(w[i]*sizeof(long));}
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++)
      g<<d[i]%N<<" ";
return 0;}