type edge=record
u,v,c:longint;
end;
var
n,m,s,i:longint;
e:array[1..100000] of edge;
d:array[1..1000] of longint;
procedure init;
var
i,a,b:longint;
begin
read(n,m,s);
for i:=1 to m do
with e[i] do
read(u,v,c);
end;
function relaxed(u,v,c:longint):boolean;
begin
if (d[u]<>maxlongint)and(d[v]>d[u]+c)then
begin
d[v]:=d[u]+c;
exit(true);
end;
exit(false);
end;
function bellmanford(s:longint):boolean;
var
k,i:longint;
flag:boolean;
begin
for i:=1 to n do
d[i]:=maxlongint;
d[s]:=0;
for k:=1 to n-1 do
begin
flag:=false;
for i:=1 to m do
if relaxed(e[i].u,e[i].v,e[i].c) then flag:=true;
if not flag then break;
end;
for i:=1 to m do
if relaxed(e[i].u,e[i].v,e[i].c) then exit(false);
exit(true);
end;
begin
init;
if not bellmanford(s) then writeln('-1')
else
begin
for i:=1 to n do
if d[i]=maxlongint then writeln('NoPath')
else writeln(d[i]);
end;
end.