[Usaco2007 Feb]Cow Party

农场中有 $N$ 个牛棚，每个牛棚里都有一头奶牛。所有奶牛都要前往牛棚 $X$ 参加派对。

牛棚之间共有 $M$ 条单向道路。第 $i$ 条道路从牛棚 $A_i$ 通往牛棚 $B_i$ ，通过这条道路需要花费 $T_i$ 的时间。

无论是前往牛棚 $X$ 参加派对，还是在派对结束后返回原来的牛棚，每头奶牛都会选择用时最少的路线。

请计算所有奶牛中，往返派对所需总时间的最大值。

输入格式

第一行包含三个以空格分隔的整数 $N$ 、 $M$ 和 $X$ ，分别表示牛棚数量、单向道路数量以及举办派对的牛棚编号。

接下来 $M$ 行，每行包含三个以空格分隔的整数 $A_i$ 、 $B_i$ 和 $T_i$ ，表示一条从牛棚 $A_i$ 通往牛棚 $B_i$ 、通过时间为 $T_i$ 的单向道路。

输出一行一个整数，表示所有奶牛前往派对并返回原牛棚所需总时间的最大值。

共有 $4$ 头奶牛参加派对，农场中有 $8$ 条单向道路，派对在编号为 $2$ 的牛棚举行。

编号为 $4$ 的牛棚中的奶牛可以直接前往派对所在地，用时为 $3$ ；返程的最短路线经过编号为 $1$ 和 $3$ 的牛棚，用时为 $7$ 。因此，它往返所需的总时间为 $10$ 。

本题为 USACO $2007$ 年二月试题「Cow Party」，题面与测试数据整理自 BZOJ $1631$ 。