UVA1537 Picnic Planning

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` 是兄弟俩所有汽车的总行驶里程。

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