大胡子的烦恼

Time Limit: 2000 ms

Memory Limit: 65535 ms

Description

大胡子是一位非常有激情的旅行家,他经常一个人开着卡车到处跑,但他更喜欢和一群人开着几辆卡车到处跑,于是他创办了卡车联盟。这个联盟经常举办长途卡车旅行,而大胡子则担当队长。 每次旅行,大胡子都要想方设法使所有人的卡车跑的总里程数最且因为景点能停的车位n是有限的,于是他倡议大家能拼车就拼车。当然,一定要确保所有的人都是坐车去的(开车坐车无所谓)。卡车容积不限。 因为每个成员都有辆卡车,且成员家里能停的车位不限,所以他们可以先开车到某个成员家里,再和他同乘一辆车到下一个地点。也可以在家里等人接自己。当然,也可以和其他车辆汇合在某一个地点,在同乘一辆车。请你帮抓狂的大胡子计算一下把所有人送到景点(设景点为Park)所有人的卡车所需要行驶的最小里程。注意:所有的道路都是无向的!且人数小于五十,每个人的住址都不相同.

Input

第一行输入测试数据个数t 下面每一组测试数据中第一行输入n,代表连接各个成员(包括景点)的道路条数。 下面n行中 先输入道路的起点,终点,道路的长度。中间用空格隔开。 最后输入景点能够停车的数目。

Output

最小里程数,一行一个数。

Sample Input

1
10
Zhangke Berk 32
zhangke Park 57
zhangke Eduardo 43
Berk Park 19
Berk Clemenzi 82
Clemenzi Park 65
Clemenzi Herb 90
Clemenzi Eduardo 109
Park Herb 24
Herb Eduardo 79
3

Sample Output

183

Hint

Source

ChenYi&LiChangming&NiChen

提交代码