소풍 계획

곡예 형제단(Contortion Brothers)은 아무리 작은 차에도 원하는 만큼 많은 인원을 밀어 넣는 재주로 세계적으로 유명한 서커스 광대들이다. 비수기가 되면 형제들은 동네 공원(Park)에서 열리는 연례 모임에 함께 모인다.

형제들은 좁은 공간을 마다하지 않을 뿐 아니라 돈에도 인색해서, 모든 차가 달리는 총 주행 거리(마일)의 합이 최소가 되는 방법으로 모임 장소까지 이동하려 한다(연료비와 차량 마모 등을 아끼기 위해서다). 이를 위해 필요한 만큼 차에 서로를 욱여넣어 사용하는 차의 수를 줄인다. 그 결과 여러 형제가 한 형제의 집으로 모여, 한 대만 남기고 나머지 차는 그 집에 둔 뒤 남은 한 대에 다 함께 타는 식으로 이동하는 경우가 많다.

다만 공원에는 제약이 하나 있다. 소풍 장소의 주차장에는 정해진 대수만큼의 차만 세울 수 있으므로, 이 점도 전체 최소화 계산에 반영해야 한다. 또한 입장료 때문에 어떤 형제의 차든 일단 공원에 도착하면 그대로 머무른다. 즉 승객을 내려 주고 다른 형제를 태우러 다시 나가는 일은 없다.

형제들의 집과 공원을 잇는 도로망이 주어질 때, 모든 형제가 공원에 도착하도록 하면서 공원에 도착하는 차의 수가 주차장 수용 대수를 넘지 않는다는 조건 아래에서, 모든 차의 총 주행 거리의 최솟값을 구하여라.

입력의 첫 줄에는 뒤따르는 테스트 케이스의 수를 나타내는 양의 정수 하나가 주어진다. 이 줄 다음에는 빈 줄이 하나 있으며, 연속한 두 테스트 케이스 사이에도 빈 줄이 하나씩 있다.

각 테스트 케이스는 다음과 같이 구성된다.

• 첫 줄에는 형제들 사이 또는 형제와 공원 사이의 도로 연결 개수 $n$이 주어진다.
• 이어지는 $n$개의 줄에는 각각 하나의 연결이 name1 name2 dist 형식으로 주어진다. name1과 name2는 두 형제의 이름이거나, 한쪽이 단어 Park이고 다른 한쪽이 형제의 이름이다(순서는 무관). dist는 둘 사이의 거리를 나타내는 정수이다.
• 모든 도로는 양방향이며, dist는 항상 양수이다.
• 마지막 줄에는 소풍 장소 주차장에 세울 수 있는 차의 수 $s$가 정수로 주어진다.

형제의 수는 최대 20명이고, 이름의 길이는 최대 10글자이다. 모든 형제의 집에서 공원까지 가는 경로가 존재하며, 각 테스트 케이스에는 항상 해가 존재한다고 가정해도 된다.

각 테스트 케이스에 대해 다음 형식의 한 줄을 출력한다.

Total miles driven: xxx

여기서 xxx는 모든 형제의 차가 달린 총 주행 거리이다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣어 구분한다.