program algoritmul_dijkstra;
  var f1,f2:text;
      a:array [1..50000] of longint;
      b,c:array [1..250000] of longint;
      cost:array [1..250000] of integer;
      n,m,i:longint;
      bool:boolean;
begin
  assign(f1,'dijkstra.in');
  reset(f1);
  assign(f2,'dijkstra.out');
  rewrite(f2);
  readln(f1,n,m);
  for i:=1 to m do readln(f1,b[i],c[i],cost[i]);
  for i:=2 to n do a[i]:=-1;
  bool:=true;
  while bool do
    begin
      bool:=false;
      for i:=1 to m do
        if (a[b[i]]<>-1) and ((a[c[i]]=-1) or (a[c[i]]>a[b[i]]+cost[i])) then
           begin
             a[c[i]]:=a[b[i]]+cost[i];
             bool:=true;
           end;
    end;
  for i:=2 to n do
    if a[i]=-1 then write(f2,0,' ')
               else write(f2,a[i],' ');
  close(f1);
  close(f2);
end.