#include<fstream.h>
#define N 50001
#define M 250001
long n,m,i,j,k,d[N],l,t,p=0,co,deg[N]={0},*g1[N],*g2[N],a[M],b[M],e[M],q[M],u=0,o;
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],deg[a[k]]++;
for(i=1;i<=n;deg[i++]=0)     
      {d[i]=N;
      g1[i]=(long*)malloc((deg[i]+1)*sizeof(long));
      g2[i]=(long*)malloc((deg[i]+1)*sizeof(long));}
for(k=1;k<=m;k++)
      g1[a[k]][deg[a[k]]]=b[k],g2[a[k]][deg[a[k]]]=e[k],deg[a[k]]++;     
d[1]=0;
q[u++]=1;
while(p!=u)
      {t=q[p++];
      for(j=0;j<deg[t];j++)
      if(d[g1[t][j]]>d[t]+g2[t][j])
             d[g1[t][j]]=d[t]+g2[t][j],q[u++]=g1[t][j];}
for(o=2;o<=n;o++)
      g<<d[o]%N<<" ";
f.close();
g.close();
return 0;}