#1631. [Usaco2007 Feb]Cow Party

题目描述

农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？

输入格式

第1行:三个用空格隔开的整数.

第2行到第M+1行,每行三个用空格隔开的整数: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  

数据范围与提示

样例说明:

共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.

第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.