const fi        =       'dijkstra.in';
      fo        =       'dijkstra.out';
      maxn      =       55555;
      maxm      =       255555;
type edge       =       record u,v,c : longint; end;
var ke,a        :       array[0..maxm] of longint;
    start,d     :       array[0..maxn] of longint;
    queue       :       array[0..maxn] of longint;
    inq         :       array[0..maxn] of boolean;
    c           :       array[0..maxm] of edge;
    oo,n,m      :       longint;
    dau,cuoi    :       longint;
    tf          :       text;

procedure init;
var i,j : longint;
 begin
  assign(tf,fi);
  reset(tf);
  read(tf,n,m);
  for i := 1 to m do
   with c[i] do
    begin
     readln(tf,u,v,c);
     inc(start[u]);
    end;
  for i := 2 to n+1 do start[i] := start[i] + start[i-1];

  for i := 1 to m do
   with c[i] do
    begin
     ke[start[u]] := v;
     a[start[u]] := c;
     dec(start[u]);
    end;
  close(tf);
 end;

procedure push(u:longint);
 begin
  if inq[u] then exit;
  inc(cuoi);
  if cuoi > maxn then cuoi := 1;
  queue[cuoi] := u;
  inq[u] := true;
 end;

procedure pop(var u : longint);
 begin
  inc(dau);
  if dau > maxn then dau := 1;
  u := queue[dau];
  inq[u] := false;
 end;

procedure process;
var i,j,u,v : longint;
 begin
  fillChar(d,SizeOf(d),$7F);
  oo := d[1];
  d[1] := 0;
  push(1);
  while dau <> cuoi do
   begin
    pop(u);
    for i := start[u]+1 to start[u+1] do
     begin
      v := ke[i];
      if d[v] > d[u] + a[i] then
       begin
        d[v] := d[u] + a[i];
        push(v);
       end;
     end;
   end;
 end;

procedure result;
var i : longint;
 begin
  assign(tf,fo);
  reWrite(tf);
  for i := 2 to n do
   if d[i] = oo then Write(tf,0,' ') else Write(tf,d[i],' ');
  close(tf);
 end;

begin
 init;
 process;
 result;
end.