记录编号	61513	评测结果	AAAAAAAAAAAAAAAAA
题目名称	网络探测	最终得分	100
用户昵称	CAX_CPG	是否通过	通过
代码语言	Pascal	运行时间	0.035 s
提交时间	2013-06-11 14:10:57	内存使用	5.14 MiB

program ping;
var
   a,d,c,b		       : array[0..1000]of longint;
   ef,et,el		       : array[1..100000]of longint;
   q			       : array[1..1000000]of longint;
   v			       : array[0..1000]of boolean;
   head,tail,x,y,z,tot,i,n,m,t : longint;

procedure add(x,y,z : longint);
begin
   inc(tot);
   el[tot]:=z;et[tot]:=y;
   ef[tot]:=a[x];a[x]:=tot;
end; { add }

begin
   assign(input,'ping.in');reset(input);
   assign(output,'ping.out');rewrite(output);
   readln(n,m,t);
   for i:=1 to m do
   begin
      readln(x,y,z);
      add(x,y,z);
      add(y,x,z);
   end;
   head:=0;tail:=1;q[1]:=0;
   fillchar(d,sizeof(d),127);d[t]:=0;
   fillchar(c,sizeof(c),127);c[0]:=0;
   while head<>tail do
   begin
      inc(head);
      x:=q[head];
      i:=a[x];
      while i<>0 do
      begin
	 if c[et[i]]>c[x]+1 then
	 begin
	    c[et[i]]:=c[x]+1;
	    inc(tail);
	    q[tail]:=et[i];
	 end;
	 i:=ef[i];
      end;
   end;
   if c[t]>10 then begin writeln('no');close(output);halt;end;
   head:=0;tail:=1;q[1]:=t;
   while head<>tail do
   begin
      inc(head);
      x:=q[head];v[x]:=false;
      i:=a[x];
      while i<>0 do
	 begin
	    if c[et[i]]+b[x]<10 then
	       if d[et[i]]>d[x]+el[i]then
	       begin
		  d[et[i]]:=d[x]+el[i];
		  b[et[i]]:=b[x]+1;
		  if not v[et[i]]then
		  begin inc(tail);q[tail]:=et[i];v[et[i]]:=true;end;
	       end;
	    i:=ef[i];
	 end;
   end;
   writeln(d[0]);close(output);
end.