记录编号	350399	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	citrono	是否通过	通过
代码语言	Pascal	运行时间	0.009 s
提交时间	2016-11-15 19:14:50	内存使用	0.24 MiB

var
 i,j,n,start,m,x,y:longint;
 d,len:array[0..100] of longint;
 a,s:array[0..100,0..100]of longint;
 f:array[0..100]of boolean;
procedure print(mb:longint);
 var
  i:longint;
 begin
  writeln(mb,':');
  write('path:');
  for i:=1 to len[mb] do write(s[mb,i],' ');
  writeln(mb);
  writeln('cost:',d[mb]);
 end;
procedure dijkstra(mb:longint);
 var
  i,j,min,k,t:longint;
 begin
  for i:=0 to n-1 do
   begin
    len[i]:=1;
    s[i,len[i]]:=start;
    d[i]:=a[start,i];
    f[i]:=false;
   end;
  f[start]:=true;
  for i:=2 to n do
   begin
    k:=-1;
    min:=maxint;
    for j:=0 to n-1 do
     if (not f[j])and(d[j]<min)then
      begin
       min:=d[j];k:=j;
      end;
    if (k=mb)or(k=-1)or(min=maxint) then
     begin
      exit;
     end;
    f[k]:=true;
    for j:=0 to n-1 do
     begin
      if(not f[j])and(d[k]+a[k,j]<d[j])then
       begin
        d[j]:=d[k]+a[k,j];
        len[j]:=len[k];
        for t:=2 to len[k] do s[j,t]:=s[k,t];
        inc(len[j]);s[j,len[j]]:=k;
       end;
     end;
   end;
 end;
begin
 assign(input,'djs.in');reset(input);
 assign(output,'djs.out');rewrite(output);
 read(n,m,start);
 for i:=0 to n-1 do
  for j:=0 to n-1 do
   a[i,j]:=maxint;
 for i:=1 to m do
  begin
   read(x,y);
   read(a[x,y]);
  end;
 for i:=0 to n-1 do
  if i<>start then
   begin
    dijkstra(i);
    if (d[i]<>0)and(d[i]<>maxint) then print(i)
     else
      begin
       writeln(i,':');
       writeln('no');
      end;
   end
  else
   begin
    writeln(i,':');
    writeln('no');
   end;
 close(input);close(output);
end.