记录编号	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.