program bell_man_ford;
const fi='bellmanford.in';
      fo='bellmanford.out';
type li=record
   nod,val:longint;
    end;
var f,g:text;
    v:array of array of  li;
    bufin,bufout:array[1..65000] of char;
    n,m,a,b,c1,i,st,sf,nd:longint;
    c,viz,s,v1:array[1..50001] of longint;
    cd:array[1..1000000] of longint;
begin

   assign(f,fi);
   reset(f);
   assign(g,fo);
   rewrite(g);
   settextbuf(f,bufin);
   settextbuf(f,bufout);
   read(f,n,m);
   setlength(v,n+1,1);

   for i:=1 to m do
     begin
      read(f,a,b,c1);
      inc(c[a]);
      setlength(v[a],c[a]+1);
      v[a,c[a]].nod:=b;
      v[a,c[a]].val:=c1;
     end;
    st:=0;
    sf:=1;
    for i:=2 to n do
        s[i]:=maxlongint;
    s[1]:=0;
    cd[1]:=1;
    viz[1]:=1;
    v1[1]:=1;
    while st<sf do
      begin
        if st=500000 then
          begin
            write(g,'Ciclu negativ!');
            close(f);
            close(g);
            exit;
          end;
         inc(st);
         nd:=cd[st];
         viz[nd]:=0;
         for i:=1 to c[nd] do
           begin
            if s[nd]+v[nd,i].val<s[v[nd,i].nod] then
               begin
                 s[v[nd,i].nod]:=s[nd]+v[nd,i].val;
                 if viz[v[nd,i].nod]=0 then
                   begin
                     inc(sf);
                     cd[sf]:=v[nd,i].nod;
                     viz[v[nd,i].nod]:=1;
                   end;
                end;
           end;

       end;
     for i:=2 to n do
        if s[i]=maxlongint then
          write(g,0,' ')
       else
         write(g,s[i],' ');
   close(f);
   close(g);
end.