度限制最小生成树。

先不加连跟的边，跑出其他的x个最小生成森林。

用最小代价的边链接根和森林，得到x度时的最小生成树。

如果度限制小于x，无解

如果度大于x，我们需要继续加链接根的边。

每一次枚举所有可能可以加入的边，找到加入后形成的环上不与根链接的边中最长的那一条删掉。在所有能加入的边中取最优的。这样我们可以构造出x+1度的最小生成树

一直构造即可。

#include<bits/stdc++.h>
using namespace std;
#define orz cout<<"lytcltcltcltcltcltcl"<<endl
inline int r(){int s=0,k=1;char c=getchar();while(!isdigit(c)){if(c=='-')k=-1;c=getchar();}while(isdigit(c)){s=s*10+c-'0';c=getchar();}return s*k;}
int t,n,lst,head[10005],cnt,m,dis[10005],fa[10005],ans,b[10005],mini[10005],maxi[105],times,f[10001],rest,valid[10005],root,link[10005],g[105];
map<string,int>mp;
struct node
{
	int from,to,dis,next,link;
	void clear()
	{
		from=to=dis=next=link=0;
	}
}a[10001];
node e[10001];
void add_edge(int from,int to,int dis)
{
	a[++cnt].to=to;
	a[cnt].next=head[from];
	head[from]=cnt;
	a[cnt].dis=dis;
	a[cnt].from=from;
}
bool cmp(node x,node y)
{
	return x.dis<y.dis;
}
int father(int x)
{
	if(fa[x]!=x)fa[x]=father(fa[x]);
	return fa[x];
}
void dfs1(int u)
{
	b[u]=times;
	for(int i=head[u];i;i=a[i].next)
	{
		int v=a[i].to;
		if(!b[v])dfs1(v);
	}
}
void dfs2(int u,int fa,int deep,int k)
{
//	cout<<"dfs"<<u<<endl;
	b[u]=times;
	maxi[u]=deep;
	g[u]=k;
	for(int i=head[u];i;i=a[i].next)
	{
		int v=a[i].to;
		if(v==fa)continue;
		if(link[i])continue;
		if(u!=root)
		{
			if(deep<a[i].dis)dfs2(v,u,a[i].dis,i);
			else dfs2(v,u,deep,k);
		}
		else dfs2(v,u,0,0);
	}
}
void work()
{
	m=r();
	string x,y;
	int z;
	
	for(int i=1;i<=2*m;i++)
	{
		a[i].clear();
		e[i].clear();
	}
	
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		cin>>z;
		if(mp[x]==0)
		{
			n++;
			mp[x]=n;
		}
		if(mp[y]==0)
		{
			n++;
			mp[y]=n;
		}
		int xx=mp[x],yy=mp[y];
		e[i].from=xx;e[i].to=yy;e[i].dis=z;
		add_edge(xx,yy,z);
		add_edge(yy,xx,z);
	}
	
	
	root=mp["Park"];
	for(int i=head[root];i;i=a[i].next)e[(i+1)/2].link=1;
	memset(head,0,sizeof(head));cnt=1;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		if(e[i].link)continue;
		int x=e[i].from,y=e[i].to;
		int fax=father(x),fay=father(y);
		if(fax==fay)continue;
		fa[fax]=fay;
		ans+=e[i].dis;
		add_edge(e[i].from,e[i].to,e[i].dis);
		add_edge(e[i].to,e[i].from,e[i].dis);
//		cout<<"add"<<e[i].from<<' '<<e[i].to<<' '<<e[i].dis<<endl;
	}
//	cout<<mp["Park"];
	
	
	memset(mini,0x3f,sizeof(mini));
	for(int i=1;i<=n;i++)
	{
		if(!b[i]&&i!=root)
		{
			times++;
			dfs1(i);
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(!e[i].link)continue;
		int x=e[i].from,y=e[i].to;
		if(y==root)swap(x,y);
		if(mini[b[y]]>e[i].dis)
		{
			mini[b[y]]=e[i].dis;
			f[b[y]]=i;
		}
	}
	for(int i=1;i<=times;i++)
	{
		int x=e[f[i]].from,y=e[f[i]].to,z=e[f[i]].dis;
		valid[f[i]]=1;
		add_edge(x,y,z);
		add_edge(y,x,z);
		ans+=mini[i];
//		cout<<"add"<<x<<" "<<y<<" "<<z<<endl;
	}

//	cout<<ans<<endl;	
	lst=ans;
	rest=r();
	for(int ttt=times+1;ttt<=rest;ttt++)
	{
		memset(maxi,0,sizeof(maxi));
		dfs2(root,0,0,0);//find the maxi
//		for(int i=1;i<=n;i++)
//		cout<<"maxi"<<i<<":"<<maxi[i]<<" "<<g[i]<<endl;
		
		int choose_maxi=-1e9,choose_i=0,choose_j=0;
		for(int i=1;i<=m;i++)
		{
			if(!e[i].link)continue;
			if(valid[i])continue;
			int x=e[i].from,y=e[i].to;
			if(y==root)swap(x,y);
			if(choose_maxi<maxi[y]-e[i].dis)
			{
				choose_maxi=maxi[y]-e[i].dis;
				choose_i=g[y];
				choose_j=i;
			}
		}
		
//		cout<<"get"<<choose_maxi<<" "<<e[choose_j].dis<<" "<<a[choose_i].dis<<endl;

		lst-=choose_maxi;
		ans=min(ans,lst);
		link[choose_i]=1;
		link[choose_i^1]=1;
		add_edge(e[choose_j].from,e[choose_j].to,e[choose_j].dis);
		add_edge(e[choose_j].to,e[choose_j].from,e[choose_j].dis);
	}
	
	cout<<"Total miles driven: "<<ans<<"\n";
}
void init()
{
	n=lst=cnt=m=ans=times=root=rest=0;
	memset(b,0,sizeof(b));
	memset(mini,0,sizeof(mini));
	memset(maxi,0,sizeof(maxi));
	memset(head,0,sizeof(head));
	memset(dis,0,sizeof(dis));
	memset(valid,0,sizeof(valid));
	memset(g,0,sizeof(g));
	memset(f,0,sizeof(f));
	memset(fa,0,sizeof(fa));
	memset(link,0,sizeof(link));
	mp.clear();
}
int main()
{
//	freopen("a.in","r",stdin);
//	freopen("b.txt","w",stdout);
	t=r();
	while(t--)
	{
		init();
		work();
		if(t!=0)puts("");
	}
}