program bellmanford;
type pcelula=^celula;
     celula=record
        x,cost:longint;
        adr:pcelula;
     end;

var graf:array[1..50000] of pcelula;
    n,m,x,y,i,nod:word;
    cost:integer;
    f,g:text;
    piq,psq,p,aux:pcelula;
    dist:array[1..50000] of longint;
    inq:array[1..50000] of boolean;
    nrinq:array[1..50000] of word;
    ciclu:boolean;


begin
assign(f,'bellmanford.in'); reset(f);
assign(g,'bellmanford.out'); rewrite(g);
readln(f,n,m);
for i:=1 to n do
        begin
        dist[i]:=maxlongint;
        inq[i]:=false;
        nrinq[i]:=0;
        graf[i]:=nil;
        end;
for i:=1 to m do
        begin
        readln(f,x,y,cost);
        new(p);
        p^.cost:=cost;
        p^.x:=y;
        p^.adr:=graf[x];
        graf[x]:=p;
        end;

new(piq);
psq:=piq;
piq^.adr:=nil;
piq^.x:=1;
dist[1]:=0;
inq[1]:=true;
nrinq[1]:=1;
ciclu:=false;
while (piq<>nil) and (ciclu=false) do
        begin
        nod:=piq^.x;
        //inq[nod]:=false;
        //p:=piq;
        //piq:=piq^.adr;
        //dispose(p);
        //nrinq[nod]:=nrinq[nod]+1;
        p:=graf[nod];
        while p<>nil do
                        begin
                        if (dist[nod]+p^.cost<dist[p^.x]) then
                                begin
                                dist[p^.x]:=dist[nod]+p^.cost;
                                if inq[p^.x]=false then
                                        begin
                                        new(aux);
                                        aux^.adr:=nil;
                                        aux^.x:=p^.x;
                                        psq^.adr:=aux;
                                        psq:=aux;
                                        inq[p^.x]:=true;
                                        nrinq[p^.x]:=nrinq[p^.x]+1;
                                        if nrinq[p^.x]=n then ciclu:=true;
                                        end;
                                end;
                        p:=p^.adr;
                        end;
        inq[nod]:=false;
        p:=piq;
        piq:=piq^.adr;
        dispose(p);
        end;
if ciclu=true then
        write(g,'Ciclu negativ!')
else for i:=2 to n do
        write(g,dist[i],' ');
close(f); close(g);
end.