农场派对

题目描述:

N头牛都要去参加一场在编号为X（1≤X≤N）的牛的农场举行的派对（1≤N≤3000），农场之间有M（1≤M≤100，000）条有向路，每条路长Ti（1≤Ti≤100）。

每头牛参加派对后都必须回到家，每头牛都会选择最短路。求这N头牛的最短路（一个来回）中最长的一条的长度。

输入格式:

第一行，3个空格分开的整数N,M,X。

第二行到M+1行： 3个用空格分开的整数Ai，Bi，Ti，表示有一条从Ai到Bi的路，长度为Ti。

输出格式:

一行，最长的最短路的长度。

样例输入:

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

样例输出:

10

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO07FEB