program VijosP1503;

var
n, m, s, i, s0: longint;
pn, v, Count, q: array[1..1000] of longint;
tt: array[1..10000] of boolean;
d: array[1..1000] of int64;
cost: array[1..1000, 1..1000] of longint;
p: array[1..1000, 1..100000] of longint;

procedure init;
var
i, x, y, z: longint;
begin
readln(n, m, s);
s0 := s;
fillchar(pn, sizeof(pn), 0);
for i := 1 to m do
begin
readln(x, y, z);
Inc(pn[x]);
p[x, pn[x]] := y;
cost[x, y] := z;
end;
end;

procedure SPFA;
var
i, j, h, t, x, y: longint;
begin
fillchar(v, sizeof(v), 0);
fillchar(Count, sizeof(Count), 0);
for i := 1 to n do
d[i] := 184467440737095516;
fillchar(q, sizeof(q), 0);
h := 0;
t := 0;
Inc(t);
q[t] := s;
v[s] := 1;
d[s] := 0;
Count[s] := 1;
tt[s]:=true;
while h <> t do
begin
h := (h mod n) + 1;
x := q[h];
v[x] := 0;
for j := 1 to pn[x] do
begin
y := p[x, j];
if d[x] + cost[x, y] < d[y] then
begin
d[y] := d[x] + cost[x, y];
if v[y] = 0 then
begin
t := (t mod n) + 1;
q[t] := y;
v[y] := 1;
Inc(Count[y]);
tt[y]:=true;
if Count[y] > n then
begin
writeln(-1);
//readln;
halt;
end;
end;
end;
end;
end;
end;

begin
init;
SPFA;
fillchar(tt, sizeof(tt), False);
for i := 1 to n do
if not tt[i] then
begin
s := i;
SPFA;
end;
fillchar(tt, sizeof(tt), False);
s := s0;
SPFA;
for i := 1 to n do
begin
if not tt[i] then
writeln('NoPath')
else
writeln(d[i]);
end;
//readln;
end.