$1..N$으로 번호가 붙은 $N$개의 농장 ($1 \le N \le 1000$)에서 각각 소 한 마리가 농장 $X$ ($1 \le X \le N$)에서 열릴 큰 소 파티에 참가합니다. 농장 쌍을 연결하는 일방통행 도로가 총 $M$개 ($1 \le M \le 100,000$) 있으며, 도로 $i$를 지나는 데 $T_i$ ($1 \le T_i \le 100$) 시간 단위가 걸립니다.

각 소는 파티까지 걸어가고, 파티가 끝나면 자신의 농장으로 돌아와야 합니다. 모든 소는 게으르므로 시간이 가장 짧은 최적 경로를 선택합니다. 도로가 일방통행이므로 돌아오는 경로는 파티에 가는 경로와 다를 수 있습니다.

모든 소 중에서 파티까지 갔다가 돌아오는 데 걸리는 가장 긴 시간은 얼마인가요?

입력

표준 입력에서 입력을 읽습니다.

• 1번째 줄: 공백으로 구분된 세 정수 $N$, $M$, $X$가 순서대로 주어집니다.

$2..M+1$번째 줄: $i+1$번째 줄은 공백으로 구분된 세 정수 $A_i$, $B_i$, $T_i$로 도로 $i$를 설명합니다. 이 도로는 농장 $A_i$에서 농장 $B_i$로 이어지며, 지나는 데 $T_i$ 시간 단위가 걸립니다.

출력

표준 출력에 출력합니다.

• 1번째 줄: 어느 한 소가 걸어야 하는 시간의 최댓값을 나타내는 정수 하나.

예제

입력 1

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

출력 1

10

참고

소 $4$는 파티에 바로 가고 ($3$ 단위), 농장 $1$과 $3$을 거쳐 돌아오므로 ($7$ 단위), 총 $10$ 시간 단위가 걸립니다.

문제 출처: USACO 2007 February Silver