type muchie=record
       x,y,cost:longint;
     end;

var n,m,i:longint;
    e:array[0..250002] of muchie;
    d:array[0..50002] of longint;
    ok:boolean;


begin
  assign(input,'bellmanford.in');
  reset(input);
  assign(output,'bellmanford.out');
  rewrite(output);

  readln(n,m);
  for i:=1 to m do begin
    readln(e[i].x,e[i].y,e[i].cost);
  end;

  for i:=2 to n do d[i]:=2000000000;

  repeat
    ok:=false;
    for i:=1 to m do
      if d[e[i].y]>d[e[i].x]+e[i].cost then begin
        d[e[i].y]:=d[e[i].x]+e[i].cost;
        ok:=true;
       end;
  until not ok;

  for i:=2 to n do write(d[i],' ');

  close(input);
  close(output);
end.