记录编号	525733	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	zhy	是否通过	通过
代码语言	Pascal	运行时间	0.012 s
提交时间	2018-12-06 17:59:00	内存使用	0.22 MiB

var
  n,m,s:integer;
  a,b,c:array[1..10000] of integer;
  ph1,ph2:array[1..100] of integer;
  sum1,sum2,bs1,bs2:integer;
  ok,yes:boolean;
  i,j,temp:integer;
function ss(x,y:integer):integer;
var i:integer;
begin
  for i:=1 to m do if (a[i]=x) and (b[i]=y) then exit(c[i]);
  ss:=0;
end;
procedure gogo(zd:integer);
var
  i,j,t:integer;
  cf:boolean;
begin
  for i:=0 to n-1 do
  begin
    cf:=false;
    for j:=1 to bs1 do if ph1[j]=i then cf:=true;
    if cf then continue;
    t:=ss(ph1[bs1],i);
    if (t>0) and ((not ok) or (ok and ((sum1+t)<sum2))) then
    begin
      inc(bs1); ph1[bs1]:=i; sum1:=sum1+t;
      if i=zd then
      begin
        if (ok and (sum1<sum2)) or (not ok) then
        begin
          bs2:=bs1; ph2:=ph1; sum2:=sum1; ok:=true;
        end;
      end else gogo(zd);
      dec(bs1); sum1:=sum1-t;
    end;
  end;
end;
begin
  assign(input,'djs.in'); reset(input);
  assign(output,'djs.out'); rewrite(output);
  readln(n,m,s);
  for i:=1 to m do readln(a[i],b[i],c[i]);
  for i:=0 to n-1 do
  begin
    sum1:=0; ok:=false;
    bs1:=1; ph1[bs1]:=s;
    yes:=false;
    for j:=1 to m do if b[j]=i then begin yes:=true; break; end;
    temp:=ss(s,i);
    if temp>0 then
    begin
      sum2:=temp; ok:=true;
      bs2:=2; ph2[1]:=s; ph2[2]:=i;
    end;
    if (i<>s) and yes then gogo(i);
    writeln(i,':');
    if ok then
    begin
      write('path:');
      for j:=1 to bs2 do if j<>bs2 then write(ph2[j],' ') else writeln(ph2[j]);
      writeln('cost:',sum2);
    end else writeln('no');
  end;
  close(input); close(output);
end.