This page is still under construction.

Parts of this page are still being built. What you see may change.

Museum

Time limit3sMemory limit1024 MB

Summary
In a weighted tree, find the minimum walking time to start at room x and visit exactly k distinct rooms, ending anywhere.
Level

Medium7 of 10

Topics
Tree, Dynamic programming, DFS, Greedy
Solved
No attempts yet

Problem

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?

Input

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

Output the minimum time required to visit k rooms.

Constraints

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

Examples2

  1. Example 1

    Input
    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
    Expected output
    29

  2. Example 2

    Input
    3 1 1
1 2 4
2 3 0
    Expected output
    0