var
  a, b, c, d: array[1..250000] of longint;
  n, m, i, j, k: longint;
  t: boolean;

procedure sw(var a, b: longint);
var
  c: longint;
begin
  c := a;
  a := b;
  b := c;
end;

procedure qs(st, dr: longint);
var
  i, j, k: longint;
begin
  i := st;
  j := dr;
  k := a[(i + j) div 2];
  while i < j do 
  begin
    while a[i] < k do inc(i);
    while a[j] > k do dec(j);
    if i <= j then begin
      if a[i] = a[j] then begin
        if b[i] > b[j] then begin
          sw(b[i], b[j]);
          sw(c[i], c[j]);
        end
      end else begin
        sw(a[i], a[j]);
        sw(b[i], b[j]);
        sw(c[i], c[j]);
      end;
      inc(i);
      dec(j);
    end;
  end;
  if st < j then qs(st, j);
  if i < dr then qs(i, dr);
end;

begin
  assign(input, 'dijkstra.in');
    assign(output, 'dijkstra.out');
  reset(input);
    rewrite(output);
  read(n, m);
  for i := 1 to m do 
  begin
    read(a[i], b[i], c[i]);
    //    if b[i]<a[i] then sw(a[i],b[i]);
  end;
  d[1] := 0;
  for i := 2 to n do d[i] := -1;
  //    qs(1,m);
    //  for i:=1 to m do
    //    writeln(a[i],' ',b[i],' ',c[i]);
  t := true;
  while t do 
  begin
    t := false;
    for i := 1 to m do 
    begin
      if d[a[i]] <> -1 then begin
        if d[b[i]] = -1 then begin
          t := true;
          d[b[i]] := d[a[i]] + c[i];
          //      e[a[i]]:=b[i];
        end;
        if (d[b[i]] > d[a[i]] + c[i]) then begin
          //      j:=d[b[i]]-d[a[i]]-c[i];
          t := true;
          d[b[i]] := d[a[i]] + c[i];
          //      e[a[i]]:=b[i];
          //      k:=b[i];
          //      while e[k]<>0 do begin
          //        dec(d[e[k]],j);
          //        k:=e[k];
          //      end;
        end;
      end;
    end;
//    for j := 1 to m do
//      write(d[j], ' ');
//    writeln;
  end;
  for i := 2 to n do if d[i] = -1 then write(0, ' ') else write(d[i], ' ');
end.