const
QN = 10000;
var
edges:array[1..1000,1..1000] of record y,w:longint;end;
lalala:array[1..1000] of longint;
check:array[1..1000] of Boolean;
f,wala:array[1..1000] of longint;
i,j,k,l,x,y,w,n,m:longint;
q:array[1..10000] of longint;
head,tail,s:longint;
begin
fillchar(lalala,sizeof(lalala),0);
read(n,m,s);
for i := 1 to m do
begin
read(x,y,w);
inc(lalala[x]);
edges[x][lalala[x]].y:=y;
edges[x][lalala[x]].w:=w;
end;
fillchar(f,sizeof(f),2);
head:=0;tail:=1;q[1]:=s;check[s]:=true;wala[s]:=1;f[s]:=0;
while head<>tail do
begin
head:=head mod QN+1;
x:=q[head];
check[x]:=false;
for i := 1 to lalala[x] do
begin
j:=edges[x][i].y;
if (f[j]>f[x]+edges[x][i].w) then
begin
inc(wala[j]);
if wala[j]>n then
begin
writeln(-1);
exit;
end;
f[j]:=f[x]+edges[x][i].w;
if check[j] then continue;
check[j] := true;
tail:=tail mod QN+1;
q[tail]:=j;
end;
end;
end;
for i := 1 to n do
if f[i]<>maxlongint then
writeln(f[i])
else
writeln('NoPath');
end.