//bellman ford
type pelem=^elem;
     elem=record
       info:word;
       next:pelem;
     end;
     lista=^nod;
     nod=record
       cost:longint;
       info:word;
       next:lista;
     end;
const inf=1 shl 30;
var fi,fo:text;
    n,m,i,j,v1,v2,cc:longint;
    first,last:pelem;
    viz:array[1..50000]of byte;
    d:array[1..50000]of longint;
    list:array[1..50000]of lista;
    p:lista;

procedure qin(vl:longint);
var p:pelem;
begin
  new(p);
  p^.info:=vl;
  p^.next:=nil;
  if first=nil then
    begin
      first:=p;
      last:=p;
    end
  else
    begin
      last^.next:=p;
      last:=p;
    end;
end;

procedure qout(var vl:longint);
var p:pelem;
begin
  vl:=first^.info;
  p:=first;
  first:=first^.next;
  dispose(p);
end;

procedure bellman;
var vl,aux:longint;
begin
  for i:=2 to n do
    d[i]:=inf;
  qin(1);
  viz[1]:=1;
  while first<>nil do
    begin
      qout(vl);
      viz[vl]:=0;
      p:=list[vl];
      while p<>nil do
        begin
          if d[p^.info]>d[vl]+p^.cost then
            begin
              d[p^.info]:=d[vl]+p^.cost;
              if viz[p^.info]=0 then
                begin
                  qin(p^.info);
                  viz[p^.info]:=1;
                end;
            end;
          p:=p^.next;
        end;
    end;
  for i:=2 to n do
    if d[i]=inf then write(fo,0,' ')
                else write(fo,d[i],' ');
end;

begin
  assign(fi,'dijkstra.in'); reset(fi);
  assign(fo,'dijkstra.out'); rewrite(fo);
  read(fi,n,m);
  for i:=1 to m do
    begin
      read(fi,v1,v2,cc);
      new(p);
      p^.info:=v2;
      p^.cost:=cc;
      p^.next:=list[v1];
      list[v1]:=p;
    end;
  bellman;
  close(fi);
  close(fo);
end.