박물관

어느 관광객이 세계 여러 지역에서 모은 깨끗한 식수를 전시하는 박물관에 들어왔다. 다행히 이 전시는 인식을 높이기 위한 임시 전시이지만, 나중에 상설 전시가 될 수도 있다.

박물관은 문과 통로로 서로 연결된 n개의 방(1번부터 n번)으로 이루어져 있다. 각 통로는 다른 방을 거치지 않고 두 방을 직접 연결한다. 박물관의 구조는 임의의 두 방 사이에 정확히 하나의 단순 경로가 존재하도록 되어 있다(중간 방을 하나 이상 거칠 수도 있다). 관광객은 현재 x번 방에 있다. 그는 박물관 지도를 가지고 있어서, 각 통로 i가 방 ai와 bi를 연결하고 그 통로를 지나는 데 ci의 시간이 걸린다는 것을 안다.

그는 x번 방을 포함하여 서로 다른 k개의 방을 방문하려고 한다. 각 방에서 보내는 시간은 무시할 수 있을 만큼 짧다. 어느 방에서 방문을 마치든 상관없다. 이때 가능한 가장 짧은 시간은 얼마인가?

첫째 줄에 정수 n, k, x가 주어진다. 다음 n−1개의 줄은 방 사이의 통로를 나타내며, 정수 ai, bi, ci가 주어진다. 이는 방 ai와 bi 사이에 통로가 있고 그 통로를 지나는 데 ci의 시간이 걸린다는 뜻이다.

k개의 방을 방문하는 데 필요한 최소 시간을 출력한다.

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