program bellmanford;
var t:array[1..3,1..500000] of longint;
    c:array[1..500000] of longint;
    d,start:array[1..50000] of longint;
    viz:array [1..50000] of 0..1;
    n,m:longint;
    bufin,bufout:array[1..1 shl 17] of char;
procedure citire;
var i,j,k,c:longint;
  begin
    assign(input,'dijkstra.in');
    assign(output,'dijkstra.out');
    reset(input);
    rewrite(output);
    readln(n,m);
    for k:=1 to m do
      begin
        readln(i,j,c);
        t[1,k]:=j;
        t[2,k]:=start[i];
        t[3,k]:=c;
        start[i]:=k;
      end;
  end;
procedure bellman(sursa:longint);
var i,st,sf,p,nod:longint;
    ok:boolean;
  begin
    for i:=2 to n do
      d[i]:=maxlongint;
    d[sursa]:=0;
    st:=0;
    sf:=1;
    c[1]:=sursa;
    while (st<sf)  do
      begin
       st:=st+1;
       nod:=c[st];
       viz[nod]:=0;
       p:=start[nod];
       while (p<>0)  do
         begin
           if d[nod]+t[3,p]<d[t[1,p]] then
                                      begin
                                        d[t[1,p]]:=d[nod]+t[3,p];
                                        if viz[t[1,p]]=0 then
                                                         begin
                                                           sf:=sf+1;
                                                           c[sf]:=t[1,p];
                                                           viz[t[1,p]]:=1;
                                                         end;
                                      end;
           p:=t[2,p];
         end;
      end;
                for i:=2 to n do
                  if d[i]<>maxlongint then
                                write(d[i],' ')
                                else
                                write(0,' ')
  end;
begin
  citire;
  bellman(1);
  close(input);
  close(output);
end.