题目描述

The Contortion Brothers 是著名的马戏团小丑组合，因其令人难以置信的能力而闻名世界——无限多个兄弟可以挤进同一辆车，即便是最小的车辆。在淡季时，兄弟们喜欢聚在当地公园参加每年的杂技演员聚会。然而，这些兄弟们不仅在空间上非常紧凑，在金钱方面也十分紧张，因此他们会尽量找到一种方法，尽量减少大家开车前往聚会的里程（从而节省汽油、减少磨损等）。为此，他们愿意尽量将自己挤进最少的汽车中，以最小化所有车辆的总行驶里程。这通常意味着很多兄弟会开车到一个兄弟的家，将除了一个车之外的所有车都留在那里，然后大家挤进剩下的那一辆车。可是，聚会的公园有一个限制：停车场只能容纳有限数量的车辆，因此停车位的限制必须纳入总的节省计算中。此外，由于公园有入场费用，一旦某个兄弟的车到达公园，它就必须停在那里；他不能把乘客卸下后再开车去接其他兄弟。因此，解决这个问题对于普通的马戏团家庭来说是一项挑战，于是你被委派来编写一个程序，帮助他们解决这个减少里程的问题。

形式化地：

给定一张 $n$ 条边的无向图，求出无向图的一棵最小生成树，满足一号节点的度数不超过给定的整数 $s$。

输入格式

第一行输入一个正整数 $t$，表示测试数据组数。

对于每一组测试样例：

第一行将包含一个整数 $n$，表示兄弟之间或兄弟与公园之间的公路连接数量。空两行后接下来 $n$ 行每行格式为“$name_1-name_2-dist$”，其中 $name_1$ 和 $name_2$ 要么是两个兄弟的名字。要么是“$Park$”这个词和一个兄弟的姓名（按任何顺序），以及 $dist$ 是它们之间的整数距离。这些道路都将是双向的。兄弟的数量最大为 $20$。

最后一行包含一个整数 $s$，用于指定可以放在野餐地点停车场的汽车。你可以假设兄弟的房子都有一条路到公园，并且每个问题都有解决方案。

输出格式

对于每个测试用例，输出必须遵循以下描述。连续两个案例之间的输出将用空行分隔。

对于每个测试用例，输出应该由以下组成：

Total miles driven: xxx

其中 xxx 是兄弟俩所有汽车的总行驶里程。

输入输出样例 #1

输入 #1

2

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

10
Alphonzo Bernardo 32
Alphonzo Park 57
Alphonzo Eduardo 43
Bernardo Park 19
Bernardo Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
1

输出 #1

Total miles driven: 183

Total miles driven: 255

说明/提示

原题面并没有对 $n$ 有任何限制。经 assert $n\le 500$。