분산 연구실에는 1부터 N까지 번호가 붙은 N개의 장치가 있다. 이 중 X번 장치는 모든 결과를 최종 확인하는 검증 장치이다.

각 장치는 자신의 측정 신호를 X번 장치로 보내고, 검증이 끝난 뒤 X번 장치에서 되돌아오는 확인 신호를 받아야 한다.

연구실에는 M개의 단방향 전송 채널이 있으며, i번째 채널을 통과하는 데에는 Ti의 시간이 걸린다.

각 장치는 측정 신호를 보낼 때 가능한 가장 빠른 전송 과정을 선택하고, 확인 신호를 받을 때도 가능한 가장 빠른 전송 과정을 선택한다.

전송 채널은 방향이 정해져 있으므로, 보내는 과정과 되돌아오는 과정에서 사용되는 채널 구성이 서로 다를 수 있다.

N개의 장치 중 측정 신호를 보내고 확인 신호를 받는 데 필요한 최소 시간의 합이 가장 큰 값을 구하라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다.

두 번째 줄부터 M+1번째 줄까지 각 전송 채널의 시작 장치, 도착 장치, 그리고 이 채널을 통과하는 데 필요한 시간 Ti가 주어진다.

Ti는 1 이상 100 이하의 정수이다.

시작 장치와 도착 장치가 같은 채널은 없으며, 같은 순서쌍에 대한 전송 채널은 최대 한 개만 주어진다.

모든 장치는 X번 장치로 신호를 보낼 수 있고, X번 장치에서 모든 장치로 확인 신호를 보낼 수 있는 데이터만 입력으로 주어진다.

출력

N개의 장치에 대해, 측정 신호를 보내고 확인 신호를 받는 데 필요한 최소 시간의 합 중 최댓값을 첫째 줄에 출력한다.

예제 입력 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