program bellford;
type arc = record
       x,y,c:integer;
     end;
 
var arce:array[0..250000]of arc;
    d:array[0..250000]of integer;
    i,n,m,j:integer;
    f:text;
 
procedure bellman;
begin
 for i:=1 to n do
  for j:=1 to m do
   if d[arce[i].x]+arce[i].c<d[arce[i].y] then
    d[arce[i].y]:=d[arce[i].x]+arce[i].c;
end;
 
begin
 assign(f,'bellmanford.in'); reset(f);
  readln(f,n,m);
  for i:=1 to m do
   readln(f,arce[i].x,arce[i].y,arce[i].c);
 close(f); 
  for i:=1 to n do d[i]:=maxlongint;
  d[1]:=0;
 
 bellman;
 assign(f,'bellmanford.out'); rewrite(f);
 for i:=2 to n do writeln(f,d[i],' ');
 close(f);
end.