ONE
시간 제한1초메모리 제한128 MB
고정된 시작점에서 출발해 트리의 모든 도로를 한 번 이상 지나가는 데 필요한 최소 연료(끝나는 지점은 임의)를 구하는 문제입니다.
문제
도시는 교차로들과 그것들을 잇는 도로들로 이루어져 있다.
폭설이 내린 뒤, 눈을 치워야 하는 도로들은 다음 조건을 만족하도록 선택된다. 도로의 개수는 가능한 한 적으면서도 여전히 모든 두 교차로가 서로 연결되어 있어야 한다. 즉, 임의의 두 교차로 사이에는 정확히 하나의 경로가 존재한다. (교차로가 N개이면 이는 정확히 N-1개의 도로로 이루어진 트리를 뜻한다.)
제설차 한 대와 운전자 미르코가 있으며, 출발 위치는 어느 한 교차로이다. 제설차는 1미터를 달릴 때마다 연료 1리터를 소모하며(이미 눈을 치운 도로를 지나가더라도 마찬가지다), 목록에 있는 모든 도로의 눈을 치워야 한다. 모든 도로의 눈을 다 치우면, 제설차는 마지막으로 방문한 교차로에 주차한다.
모든 도로의 눈을 치우기 위해 제설차가 소모하는 연료의 최솟값을 구하여라.
입력
첫째 줄에 두 정수 N과 S (1 <= N <= 100000, 1 <= S <= N)가 주어진다. N은 교차로의 총 개수이고, S는 제설차가 출발하는 교차로의 번호이다. 교차로는 1부터 N까지의 번호로 구분된다.
다음 N-1개의 줄에는 각각 세 정수 A, B, C가 주어지며, 이는 교차로 A와 B가 길이 C미터인 도로로 직접 연결되어 있음을 뜻한다 (1 <= C <= 1000).
출력
모든 도로의 눈을 치우는 데 필요한 연료의 최솟값을 정수 하나로 출력한다.