시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 0 0 0 0.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

서브태스크 1 (20점)

  • n ≤ 20

서브태스크 2 (25점)

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

서브태스크 3 (35점)

  • 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

채점 및 기타 정보

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