시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

도로와 도로들을 잇는 교차로가 있는 도시가 있다. 도시에 폭설이 내리고 시장인 Milan은 업체에 눈을 치워야 할 도로들의 목록과 함께 제설을 의뢰했다. 두번째 교차로 마다 연결되 있으면서 가능한 적은 수의 도로들을 목록으로 만들었다.(즉, 두번째 교차로 마다 하나의 길이 있다.) 제설업체에는  두 개의 제설기기와  두 명의 운전사 Mirko와 Slavko가 있고, 제설작업 시작위치는 교차로 중 하나이다.

제설기는 미터당 1리터의 연료를 소모하며(이미 제설된 도로를 지나가도 해당됨) 최소한의 연료를 사용하여 모든 도로의 제설작업을 완료해야 한다. 모든 도로를 제설하면 제설기는 마지막 교차로에 주차된다.Mirko와 Slavko는 같은 교차로에서 제설작업을 마무리할 수 없다.

제설기가 소모할 총 연료의 양을 구하는 프로그램을 작성하시오.

입력

첫줄에는 총 교차로의 수 N과 제설기의 시작교차의 번호 S가 주어지며 (1 ≤ N ≤ 100000, 1 ≤ S ≤ N) 교차로는 1~N까지 번호가 매겨진다.

다음 각 줄에는(N-1까지) 교차로 A, 교차로 B, 총 길이 C 3개의 정수가 공백을 구분으로 주어진다.(A교차로와 B교차로는 직선으로 연결되어 있고 직선의 총길이C는 1 ≤ C ≤ 1000 이다.)

출력

모든 거리를 제설하는데 드는 최소한의 연료량을 출력하시오.

예제 입력

5 2
1 2 1
2 3 2
3 4 2
4 5 1

예제 출력

6

예제 입력 2

5 1
1 2 1
2 3 1
3 5 1
3 4 1

예제 출력 2

5

예제 입력 3

4 1
1 3 2
1 2 3
1 4 4

예제 출력 3

11

힌트