N ( 1 <= N <= 1000)농장의 (편의상 1 ,2 .. , N) 의 대표 암소 한 마리가 X ( 1 <= X <= N) 농장에서 열리는 파티에 참석하려고 한다. 전체 M ( 1 <= M <= 100,000) 의 한 방향 길이주어지고 각 길을 가는데 Ti ( 1 <= Ti <= 100 ) 만큼의 시간이 소요된다.

모든 소들은 파티에 걸어가야 하고 파티가 마친 후에는 자기가 속한 농장으로 돌아와야 한다. 모든 소들은 게을러서 가장 최단시간으로 올수 있는 최적의 길을 선택하려고 한다.

모든 소 들 중에서 농장으로 갔다가 돌아오는 데 가장 많이 걸리는 소의 시간은 얼마인가?

입력

• 첫 번째 줄 : 정수 N , M , X 가 주어진다.
• 두 번재 줄에서 M+1 번째 줄 : i+1 번째 줄은 세 정수 Ai,Bi,Ci 가 주어진다. 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

Hint

4 -> 2 ( 3 )
2 -> 1 -> 3 -> 4 (7)

합:10

출처: USACO 2007 February Silver