#include<iostream.h>
#include<fstream.h>
#define N 50001
#define M 250001
typedef struct
{long nel,elem[M],prim,ultim;}queue;
long n,m,i,j,k,d[N],c[N],l,t,p,co,deg[N]={0},*g1[N],*g2[N],a[N],b[N],e[N];
queue q;

void push(queue &q,long x)
{q.nel++;
q.elem[q.ultim++]=x;}
       
long pop(queue &q)
{q.nel--;
return q.elem[q.prim++];}

int main()
{fstream f1("dijkstra.in",ios::in);
fstream f2("dijkstra.out",ios::out);
q.prim=q.ultim=q.nel=0;
clock_t t1,t2;
t1=clock();
f1>>n>>m;
for(k=1;k<=m;k++)
      {f1>>a[k]>>b[k]>>e[k];
      deg[a[k]]++;}
for(i=1;i<=n;deg[i++]=0)      
      {c[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;
push(q,1);
while(q.nel!=0)
      {t=pop(q);
      c[t]=0;
      for(j=1;j<deg[t];j++)
      if(d[g1[t][j]]>d[t]+d[g2[t][j]])
             {d[g1[t][j]]=d[t]+d[g2[t][j]];
             if(c[g1[t][j]]==0)
                       {c[g1[t][j]]=1;
                       push(q,g1[t][j]);}}}
for(p=2;p<=n;p++)
      f2<<d[p]%N<<" ";
f1.close();
f2.close();
return 0;}