program Bellman_Ford;
const maxn=10;
var fin,fout:text;
d,dv:array[1..maxn]of integer;
list:array[1..maxn,1..maxn]of record
de,we:integer;
end;
n,s:integer;
procedure init;
var e,i,v1,v2,w:integer;
begin
fillchar(dv,sizeof(dv),0);
fillchar(list,sizeof(list),0);
assign(fin,'D:\bellman.txt');
reset(fin);
assign(fout,'d:\bellman.out');
rewrite(fout);
readln(fin,n,e);
for i:=1 to e do
begin
readln(fin,v1,v2,w);
inc(dv[v1]);
with list[v1,dv[v1]] do
begin
de:=v2;
we:=w;
end;
end;
readln(fin,s);
close(fin);
end;
procedure bellman;
var i,j,k,v2,w:integer;
begin
for i:=1 to n do
d[i]:=maxint;
d[s]:=0;
for i:=1 to n-1 do
for j:=1 to n do
begin
for k:=1 to dv[j] do
begin
v2:=list[j,k].de;
w:=list[j,k].we;
if d[v2]>d[j]+w then d[v2]:=d[j]+w;
end;
end;
for j:=1 to n do
for k:=1 to dv[j] do
begin
v2:=list[j,k].de;
w:=list[j,k].we;
if d[v2]>d[j]+w then begin
writeln(fout,'No Answer !');
close(fout);
halt;
end;
end;
end;
procedure out;
var i:integer;
begin
for i:=1 to n do
writeln(fout,i,' : ',d[i]);
close(fout);
end;
begin
init;
bellman;
out;
end.