#include <bits/stdc++.h>
using namespace std;

struct node{
	int x,y,w;
};

struct edge{
	int id,x,y,w;
};

bool cmp(node a,node b)
{
	return (a.w < b.w);
}

map < string , int > m;
vector < node > v;
vector < edge > h;

int ans = 0,t = 0,s,cnt = 0;
int vis[35][35],g[35][35],e[35][35];

void dfs_for_edge(int now,int last,int u,int v) 
{
	for (int i = 2;i <= cnt;i++)
		if (i != last && vis[now][i])
		{
			if (last == -1 || g[now][i] > g[u][v])
			{
				h.push_back({i,now,i,g[now][i]});
				dfs_for_edge(i,now,now,i);
			}
			else
			{
				h.push_back({i,u,v,g[u][v]});
				dfs_for_edge(i,now,u,v);
			}
		}
}

int fa[35];

int get(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = get(fa[x]);
}

void kruskal()
{
	for (int i = 1;i <= cnt;i++)
		fa[i] = i;
	sort(v.begin(),v.end(),cmp);
	for (auto i : v)
	{
		if (i.x == 1 || i.y == 1) continue;
		int x = get(i.x);
		int y = get(i.y);
		if (x != y)
		{
			vis[i.x][i.y] = vis[i.y][i.x] = 1;
			if (g[1][x] < g[1][y]) fa[y] = x;
			else fa[x] = y;
			ans += i.w;
		}
	}
}

int main()
{
	int jsq;
	cin >> jsq;
	for (int asd = 1;asd <= jsq;asd++)
	{
		v.clear();
		h.clear();
		m.clear();
		ans = t = cnt = s = 0;
		int n;
		cin >> n;
		string a,b;
		int w;
		memset(fa,0,sizeof(fa));
		memset(g,0x3f,sizeof(g));
		m["Park"] = ++cnt;
		for (int i = 1;i <= n;i++)
		{
			cin >> a >> b >> w;
			if (m.find(a) == m.end()) m.insert({a,++cnt});
			if (m.find(b) == m.end()) m.insert({b,++cnt});
			v.push_back({m[a],m[b],w});
			v.push_back({m[b],m[a],w});
			g[m[a]][m[b]] = min(g[m[a]][m[b]],w);
			g[m[b]][m[a]] = min(g[m[b]][m[a]],w);
		}
		cin >> s;
		kruskal();
		for (int i = 2;i <= cnt;i++)
			if (fa[i] == i) dfs_for_edge(i,-1,-1,-1);
		for (int i = 2;i <= cnt;i++)
			if (fa[i] == i)
			{
				s--;
				fa[i] = 1;
				vis[1][i] = vis[i][1] = 1;
				ans += g[1][i];
			}
		while (s--)
		{
			int minn = 0;
			edge kun;
			for (auto i : h)
			{
				if (g[1][i.id] == 0x3f3f3f3f || vis[1][i.id]) continue;
				if (minn < i.w - g[i.id][1])
				{
					minn = i.w - g[i.id][1];
					kun = i;
				}
			}
			if (minn == 0) break;
			ans -= minn;
			vis[1][kun.id] = vis[kun.id][1] = 1;
			vis[kun.x][kun.y] = vis[kun.y][kun.x] = 0;
			dfs_for_edge(kun.id,1,-1,-1);
		}
		printf("Total miles driven: %d\n",ans);
	}
	
	return 0;
}