program dijkstra;
type hacker=record
 nod,cost:longint;
end;
var f,g:text;
    n,m,i,x,y,z,ps,pi:longint;
    a:array of array of hacker;
    c:array[1..50000] of longint;
    d:array[1..50000] of longint;

begin
 assign (f,'dijkstra.in'); reset (F);
 assign (g,'dijkstra.out'); rewrite (g);
 readln (f,n,m);
 setlength(a,n+1,1);
 for i:=2 to n do
  d[i]:=maxlongint;
 for i:=1 to m do
 begin
  readln (f,x,y,z);
  inc(a[x,0].nod);
  setlengtH(a[x],length(a[x])+1);
  a[x,a[x,0].nod].nod:=y;
  a[x,a[x,0].nod].cost:=z;
 end;
 ps:=0; pi:=1; c[1]:=1;
 while ps<pi do
 begin
  inc(ps);
  for i:=1 to a[c[ps],0].nod do
  begin
   if d[a[c[ps],i].nod]>d[c[ps]]+a[c[ps],i].cost then
   begin
    d[a[c[ps],i].nod]:=d[c[ps]]+a[c[ps],i].cost;
    inc(pi);
    c[pi]:=a[c[ps],i].nod;
   end;
  end;
 end;
 for i:=2 to n do
 begin
  if d[i]=maxlongint then
   d[i]:=0;
  write (g,d[i],' ');
 end;
 close (F); close (G);
end.