#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;}