记录编号	21394	评测结果	AAAAAAAAAA
题目名称	[USACO Feb07] 奶牛聚会	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.015 s
提交时间	2010-11-10 10:06:16	内存使用	2.50 MiB

program sparty(input,output);
 
type
  re=record
    len,en,next:longint;
  end;
 
var
  n,x,m,i,a,b,t,wh:longint;
  w:array[0..1,1..100015]of re;
  len:array[0..1]of longint;
  tail,ans:array[0..1,1..1000]of longint;
 
procedure addway(const a,b,t,wh:longint);
  begin
    inc(len[wh]);
    w[wh,tail[wh,a]].en:=b;
    w[wh,tail[wh,a]].len:=t;
    w[wh,tail[wh,a]].next:=len[wh];
    tail[wh,a]:=len[wh];
  end;
 
procedure spfa;
  var
    i,j:longint;
    q:array[1..10000]of longint;
 
  procedure expand(const c:longint);
    var
      i:integer;
    begin
      i:=c;
 
      repeat
        if ans[wh,c]+w[wh,i].len<ans[wh,w[wh,i].en] then
        begin
          ans[wh,w[wh,i].en]:=ans[wh,c]+w[wh,i].len;
 
          inc(j);
          q[j]:=w[wh,i].en;
        end;
 
        i:=w[wh,i].next;
      until i=tail[wh,c];
 
      exit;
    end;
 
  begin
    i:=1;
    j:=1;
    q[1]:=x;
 
    while i<=j do
    begin
      expand(q[i]);
      inc(i);
    end;
  end;
 
begin
  assign(input,'sparty.in');
  reset(input);
  assign(output,'sparty.out');
  rewrite(output);
 
  readln(n,m,x);
 
  for i:=1 to n do
  begin
    ans[0,i]:=maxint;
    ans[1,i]:=maxint;
    tail[0,i]:=i;
    tail[1,i]:=i;
  end;
 
  len[0]:=n;
  len[1]:=n;
  for i:=1 to m do
  begin
    readln(a,b,t);
    addway(a,b,t,0);
    addway(b,a,t,1);
  end;
 
  ans[0,x]:=0;
  ans[1,x]:=0;
 
  wh:=0;
  spfa;
  wh:=1;
  spfa;
 
  a:=0;
  for i:=1 to n do
    if ans[0,i]+ans[1,i]>a then
      a:=ans[0,i]+ans[1,i];
 
  writeln(a);
 
  close(input);
  close(output);
end.