const inf=2000000001;
    type muchie=record
          v1,v2:word;
           cost:longint;
         end;

    var f,g:text;
        d:array[1..50000] of longint;
      a:array[1..250000] of muchie;
      n,m,i:longint;
      ok:boolean;

  procedure citire;
    begin
    assign(f,'dijkstra.in');
    reset(f);
    readln(f,n,m);
    for i:=1 to m do begin
        readln(f,a[i].v1,a[i].v2,a[i].cost);
        if a[i].v1=1 then d[a[i].v2]:=a[i].cost;
      end;
      for i:=2 to n do if d[i]=0 then d[i]:=inf;
   end;
  BEGIN
    citire;
    d[1]:=0;
    repeat
      ok:=true;
      for i:=1 to m do begin
       if d[a[i].v2]>d[a[i].v1]+a[i].cost then begin
         d[a[i].v2]:=d[a[i].v1]+a[i].cost;
          ok:=false;
        end;
      end;
    until ok;
   assign(g,'dijkstra.out');
    rewrite(g);
    for i:=2 to n do if d[i]<>inf then
      write(g,d[i],' ') else write(g,'0 ');
    close(g);
  END.