Program dijkstra;
 type tip=record
        x,y,t:longint;
        end;
var a:array [0..250000] of tip;
     v:array [0..55000] of longint;
     n,m,i:longint;
     ok:boolean;
     fi,fo:text;
begin
 assign(fi,'dijkstra.in');
  assign(fo,'dijkstra.out');
 reset(fi); rewrite(fo);
 readln(fi,n,m);
  for i:=0 to m-1 do readln(fi,a[i].x,a[i].y,a[i].t);
  for i:=0 to n+2 do v[i]:=-1; v[1]:=0; ok:=true;
  while ok do begin
              ok:=false;
              for i:=0 to m do
               if ((v[a[i].x]<>-1) and (v[a[i].y]=-1)) or (v[a[i].y]>v[a[i].x]+a[i].t) then
                begin
                 v[a[i].y]:=v[a[i].x]+a[i].t;
                 ok:=false;
                 end;
                 end;
  for i:=2 to n do
   if v[i]=-1 then write(fo,'0',' ')
    else write(fo,v[i],' ');
  close(fo);
 end.