program dijkstra_cu_bellman;
const inf=maxlongint;

var t:array[0..2,1..500000] of longint;
    start,cd,viz,d:array[1..50000] of longint;
    i,j,n,m,c,x,y,st,dr,k,nod,p:longint;

begin
  assign(input,'dijkstra.in'); reset(input);
  assign(output,'dijkstra.out'); rewrite(output);
  readln(n,m);
  k:=0;
  for i:=1 to m do
    begin
      readln(x,y,c);
      inc(k);
      t[0,k]:=y;
      t[1,k]:=start[x];
      start[x]:=k;
      t[2,k]:=c;
    end;
  for i:=1 to n do
    begin
       d[i]:=inf;
    end;
  viz[1]:=1;
  d[1]:=0;
  st:=0;
  dr:=1;
  cd[1]:=1;
  while st<dr do
    begin
      inc(st);
      viz[cd[st]]:=0;
      nod:=cd[st];
      p:=start[nod];
      while p<>0 do
        begin
          if d[nod]+t[2,p]<d[t[0,p]] then
            begin
              d[t[0,p]]:=d[nod]+t[2,p];
              if viz[t[0,p]]=0 then
                begin
                  inc(dr);
                  cd[dr]:=t[0,p];
                  viz[t[0,p]]:=1;
                end;
            end;

          p:=t[1,p];
        end;
    end;

  for i:=2 to n do
    if d[i]=inf then
      write(0,' ')
        else
      write(d[i],' ');


  close(input); close(output);
end.