var a,b,c,d:array[1..250000] of longint;
    i,n,m:longint;
    x:boolean;
BEGIN
  assign(input,'dijkstra.in');
  reset(input);
  readln(n,m);
  for i:=1 to m do

      readln(a[i],b[i],c[i]);
  close(input);
 for i:=1 to n do
  d[i]:=-1;

  d[1]:=0;
  x:=true;

  while x do
    begin
      x:=false;
      for i:=1 to m do
        if (d[a[i]]<>-1) and ((d[a[i]]+c[i]<d[b[i]]) or (d[b[i]]=-1)) then
          begin
            d[b[i]]:=d[a[i]]+c[i];
            x:=true;
          end;
    end;
    assign(output,'dijkstra.out');
    rewrite(output);
  for i:=2 to n do
    if d[i]=-1 then write(0,' ')
    else
    write(d[i],' ');
    close(output);
END.