var a,b,c,d:array[1..250000] of longint;
    i,n,m:longint;
    x:boolean;
    b1,b2:array[1..1 shl 17] of char;
BEGIN
  assign(input,'dijkstra.in');
  settextbuf(input,b1);

  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');
    settextbuf(output,b2);
    rewrite(output);
  for i:=2 to n do
    if d[i]>0 then write(d[i],' ')
    else
    write(0,' ');
    close(output);
END.