시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB0000.000%

## 문제

A tourist just walked into a museum that houses a treasured collection of clean drinking water from different parts of the world. Fortunately, it is only a temporary exhibition to raise awareness but might become a permanent thing in the future.

The museum consists of n rooms (numbered from 1 to n) that are connected with each other by doors and passages. Each passage connects two rooms directly, without passing through other rooms. The layout of the museum is such that between every pair of rooms, there is exactly one simple path (possibly passing through one or more intermediary rooms). The tourist is currently located in room x. He has a map of the museum and thus knows for every passage i that it connects rooms ai and bi, and that it takes ci time to walk the length of that passage.

He would like to visit k different rooms (including the starting room x). He will spend an insignificant amount of time in every room. It doesn’t matter in which room he finishes his visit. What is the shortest possible time in which he can achieve this?

## 입력

First line contains integers n, k and x. The following n−1 lines describe passages between rooms with integers ai, bi and ci, indicating that there is a passage between rooms ai and bi that takes ci time to move through.

## 출력

Output the minimum time required to visit k rooms.

## 제한

• 1 ≤ n ≤ 10 000
• 1 ≤ k, x ≤ n
• 1 ≤ ai, bi ≤ n
• 0 ≤ ci ≤ 10 000

• n ≤ 20

## 서브태스크 2 (25점)

• k ≤ 100
• Every room has at most 3 adjacent rooms

• k ≤ 100

## 서브태스크 4 (20점)

• No additional constraints

## 예제 입력 1

11 8 3
1 3 3
3 2 5
6 4 5
1 11 3
9 1 2
9 10 2
3 7 10
6 7 1
7 8 1
7 5 1


## 예제 출력 1

29


## 예제 입력 2

3 1 1
1 2 4
2 3 0


## 예제 출력 2

0


## 채점 및 기타 정보

• 예제는 채점하지 않는다.