program vijos1053;
type pointer=^node;
node=record
link,edge:longint;
next:pointer;
end;

var i,t,j,k,m,s,head,tail,x,y,z,n:longint;
ii,p:pointer;
dl,dis,d:array[0..100000]of longint;
path:array[0..100000]of pointer;
v:array[0..100000]of boolean;

procedure build(x,y,z:longint);
var p:pointer;
begin
new(p);
p^.link:=y;
p^.edge:=z;
p^.next:=path[x];
path[x]:=p;
end;

function spfa(x:longint):boolean;
var ii:pointer;
begin
spfa:=true;
fillchar(v,sizeof(v),false);
fillchar(dl,sizeof(dl),$2f);
fillchar(d,sizeof(d),0);
v[x]:=true;dl[x]:=0;d[1]:=x;
head:=0;tail:=1;
while head<tail do
begin
inc(head);
t:=d[head];
ii:=path[t];
v[t]:=false;
while ii<>nil do
begin
if dl[ii^.link]>dl[t]+ii^.edge then
begin
dl[ii^.link]:=dl[t]+ii^.edge;

if dl[x]<0 then
begin
writeln(-1);
halt;
end;

if v[ii^.link]=false then
begin
v[ii^.link]:=true;
inc(tail);
d[tail]:=ii^.link;
end;
end;
ii:=ii^.next;
end;
end;
if dl[s]>100000000 then exit(false);
end;

begin
readln(n,m,s);
for i:=1 to m do
begin
readln(x,y,z);
if (x=y)and(z<0) then
begin
writeln(-1);
halt;
end;
build(x,y,z);
end;

fillchar(v,sizeof(v),false);
fillchar(dis,sizeof(dis),$2f);
fillchar(d,sizeof(d),0);
v[s]:=true;dis[s]:=0;d[1]:=s;
head:=0;tail:=1;
while head<tail do
begin
inc(head);
t:=d[head];
ii:=path[t];
v[t]:=false;
while ii<>nil do
begin
if dis[ii^.link]>dis[t]+ii^.edge then
begin
dis[ii^.link]:=dis[t]+ii^.edge;
if v[ii^.link]=false then
begin
v[ii^.link]:=true;
inc(tail);
d[tail]:=ii^.link;
end;
end;
ii:=ii^.next;
end;
end;
for i:=1 to n do
begin
if dis[i]>100000000 then
begin
if spfa(i) then
writeln(dl[s]) else
writeln('NoPath');
continue;
end;
writeln(dis[i]);
end;
end.