记录编号	136190	评测结果	AAAAAAAA
题目名称	旅行计划	最终得分	100
用户昵称	传奇	是否通过	通过
代码语言	Pascal	运行时间	0.004 s
提交时间	2014-11-02 16:13:09	内存使用	0.18 MiB

program cojs2;
type
  apoint=^node;
  node=record
    xb,data:longint;
    next:apoint;
  end;
var
  fa,d:array[0..1000] of longint;
  a:array[0..1000] of apoint;
  fl:array[0..1000] of boolean;
  i,j,k,m,n,v,l,r,t,tt:longint;
procedure add(l,r,t:longint);
var
  p:apoint;
begin
  new(p);
  p^.xb:=r;
  p^.data:=t;
  p^.next:=a[l];
  a[l]:=p;
end;
procedure spfa(x:longint);
var
  dui:array[0..1000] of longint;
  front,tail:longint;
  p:apoint;
begin
  fillchar(d,sizeof(d),100);
  t:=d[1];
  fillchar(fl,sizeof(fl),true);
  fillchar(fa,sizeof(fa),128);
  tt:=fa[1];
  front:=0;
  tail:=1;
  dui[1]:=v;
  d[v]:=0;
  fl[v]:=false;
  while front<>tail do
    begin
      front:=front mod 1000+1;
      p:=a[dui[front]];
      while p<>nil do
        begin
          if (d[p^.xb]>d[dui[front]]+p^.data)
            or((d[p^.xb]=d[dui[front]]+p^.data)and(dui[front]<fa[p^.xb])) then
            begin
              d[p^.xb]:=d[dui[front]]+p^.data;
              fa[p^.xb]:=dui[front];
              if fl[p^.xb] then
                begin
                  tail:=tail mod 1000+1;
                  dui[tail]:=p^.xb;
                end;
            end;
          p:=p^.next;
        end;
      fl[dui[front]]:=true;
    end;
end;
procedure dod(x:longint);
begin
  if fa[x]<>tt then
    dod(fa[x]);
  write(x,' ');
end;
begin
  assign(input,'djs.in');
  assign(output,'djs.out');
  reset(input);
  rewrite(output);

  readln(n,m,v);
  for i:=1 to m do
    begin
      readln(l,r,t);
      add(l,r,t);
    end;
  spfa(v);
  d[v]:=t;
  for i:=0 to n-1 do
    begin
      writeln(i,':');
      if d[i]=t then writeln('no')
      else
        begin
          write('path:');
          dod(fa[i]);
          writeln(i);
          writeln('cost:',d[i]);
        end;
    end;

  close(input);
  close(output);
end.