#include<iostream.h>
#include<fstream.h>
#define N 50001
#define M 250001
typedef struct
{long elem[M],nel,prim,ultim;}queue;
typedef struct nod
{long info,cost;
nod *urm;}Nod,*list;
typedef list graf[N];
list r;
graf g;
queue q;
long n,m,d[N],i,j,k,c,p,t,l;

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

void add(list &r,long x,long co)
{Nod *c=new Nod;
c->info=x;
c->cost=co;
c->urm=r;
r=c;}

int main()
{fstream f1("dijkstra.in",ios::in);
fstream f2("dijkstra.out",ios::out);
q.prim=q.ultim=q.nel=0;
f1>>n>>m;
for(i=1;i<=n;i++)
      {d[i]=N;
      g[i]=NULL;}
for(k=1;k<=m;k++)
      {f1>>l>>j>>c;
      add(g[l],j,c);}
d[1]=0;
push(q,1);
while(q.nel!=0)
      {t=pop(q);
      for(r=g[t];r!=NULL;r=r->urm)
      if(d[r->info]>d[t]+r->cost)
            {d[r->info]=d[t]+r->cost;
            push(q,r->info);}}
for(p=2;p<=n;p++)      
      f2<<d[p]%N<<" ";
f1.close();
f2.close();
return 0;}