#include<bits/stdc++.h>
using namespace std;
long long max(const long long x,const long long y){
	return x>y?x:y; 
}
const int N=2e3+1e2;
struct bcj{
	int n,f[100010],siz[100010];
	void memsets(int x){
		n=x;
		for (int i=1;i<=n;++i){
			f[i]=i;siz[i]=1;
		}
	}
	int get(int x){
		if (x==f[x]) return x;
		return f[x]=get(f[x]);
	}
	bool query(int x,int y){
		return get(x)==get(y);
	}
	void modify(int x,int y){
		x=get(x);y=get(y);
		if (x==y) return ;
		if (siz[x]>siz[y]) swap(x,y);
		f[x]=y;
		siz[y]+=siz[x];
	}
}q;
bool check(string a){
	if (a.size()==4&&a[0]=='P'&&a[1]=='a'&&a[2]=='r'&&a[3]=='k') return true;
	return false;
}
struct rec{
	int e,nex;
	long long d;
}z[2*N];
int en=1,fi[N];
void add(int s,int e,long long d){
	z[++en].e=e;
	z[en].d=d;
	z[en].nex=fi[s];
	fi[s]=en;
}
struct pai{
	int x,y;
	long long z;
}a[N];
bool cmp(const pai x,const pai y){
	return x.z<y.z;
}
bool vis[N];
string aa,bb;
int cnt,n,rt,lim;
map<string,int>t;
void init(){
	scanf("%d",&n);
	t.clear();
	for (int i=1;i<=n;++i){
		cin>>aa>>bb;
		if (t[aa]==0){
			t[aa]=++cnt;
			if (check(aa)==true) rt=cnt;
		}
		if (t[bb]==0){
			t[bb]=++cnt;
			if (check(bb)==true) rt=cnt;
		}
		a[i].x=t[aa];
		a[i].y=t[bb];
		scanf("%lld",&a[i].z);
	}
	sort(a+1,a+1+n,cmp);
	q.memsets(cnt);
	scanf("%d",&lim);
}
long long ans;
bool in[N];
long long dfs(int x,int fa,long long d,int u,int j){
	if (x==u){
		return j;
	}
	long long s;
	for (int i=fi[x];i!=0;i=z[i].nex){
		if (z[i].e==fa||in[i]==true) continue;
		if (z[i].d<d) s=dfs(z[i].e,x,d,u,j);
		else s=dfs(z[i].e,x,z[i].d,u,i);
		if (s!=-1) return s;
	}
	return -1;
}
void work(){
	for (int i=1;i<=n;++i){
		if (q.query(a[i].x,a[i].y)) continue;
		if (a[i].x==rt||a[i].y==rt){
			continue; 
		}
		q.modify(a[i].x,a[i].y);
		add(a[i].x,a[i].y,a[i].z);
		add(a[i].y,a[i].x,a[i].z);
		vis[i]=true;
		ans+=a[i].z;
	}
	for (int i=1;i<=n;++i){
		if ((a[i].x!=rt&&a[i].y!=rt)||(q.query(rt,a[i].x)&&q.query(rt,a[i].y))) continue;
		--lim;
		ans+=a[i].z;
		q.modify(a[i].x,a[i].y);
		add(a[i].x,a[i].y,a[i].z);
		add(a[i].y,a[i].x,a[i].z);
		vis[i]=true;
	}
	long long s;
	for (int i=1;i<=n;++i){
		if (lim<=0) break;
		if (vis[i]||(a[i].x!=rt&&a[i].y!=rt)) continue;
		if (a[i].x==rt) swap(a[i].x,a[i].y);
		s=dfs(a[i].x,-1,0,rt,-1);
		if (s==-1||a[i].z-z[s].d>=0) continue;
		ans=ans+a[i].z-z[s].d;
		--lim;
		in[s]=true;in[s^1]=true;
		add(a[i].x,a[i].y,a[i].z);
		add(a[i].y,a[i].x,a[i].z);
	}
	
}
void print(){
	printf("Total miles driven: %lld\n",ans);
	printf("\n");
}
int ii;
void memsets(){
	for (int i=1;i<=en;++i) in[i]=false;
	for (int i=1;i<=n;++i) vis[i]=false;
	for (int i=1;i<=cnt;++i) fi[i]=0;
	cnt=0;rt=0;ans=0;en=1;
}
int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	scanf("%d",&ii);
	for (int i=1;i<ii;++i){
		memsets();
		init();
		work();
		print();
	}
	memsets();
	init();
	work();	
	printf("Total miles driven: %lld\n",ans);
	return 0;
}