#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=25,maxm=500;

int n=0,m,s,ans;
map<string,int> id;

struct E{int x,y,c,v;}e[maxm];
bool cmp(E e1,E e2)
{
	return e1.c<e2.c;
}

int D[maxn][maxn];
int belong[maxn];int scc=0;
void dfs(int x)
{
	for(int y=1;y<=n;y++) if(D[x][y]) 
	{
		if(belong[y] || y==1) continue;
		belong[y]=belong[x];
		dfs(y);
	}
}

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

int cnt;
bool link[maxn];
void kruskal()
{
	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].x==1)
		{
			if(!link[belong[e[i].y]])
			{
				link[belong[e[i].y]]=true;
				e[i].v=true;cnt++;
				D[e[i].y][1]=D[1][e[i].y]=e[i].c;
				ans+=e[i].c;
			}
			continue;
		}
		int fx=find_fa(e[i].x),fy=find_fa(e[i].y);
		if(fx==fy) continue;fa[fx]=fy;//debug
		e[i].v=true;
		D[e[i].x][e[i].y]=D[e[i].y][e[i].x]=e[i].c;
		ans+=e[i].c;
	}
}

bool find(int x,int &fx,int &fy,int &mx)
{
	for(int y=1;y<=n;y++) if(~D[x][y])
	{
		if(y==1)
		{
			mx=D[x][y];fx=x;fy=y;
			return true;
		}
		if(find(y,fx,fy,mx))//
		{
			if(D[x][y]>mx)
			{
				mx=D[x][y];fx=x;fy=y;
			}
			return true;
		}
	}
	return false;
}

string na1,na2;
int main()
{
	id["Park"]=++n;
	cin>>m;
	memset(D,0,sizeof(D));//这里的D用来记录是否有边相连 
	for(int i=1;i<=m;i++)
	{
		cin>>na1>>na2>>e[i].c;
		if(id.find(na1)==id.end()) id[na1]=++n;e[i].x=id[na1];
		if(id.find(na2)==id.end()) id[na2]=++n;e[i].y=id[na2];
		D[e[i].x][e[i].y]=D[e[i].y][e[i].x]=1;//debug 双向边 
		if(e[i].x>e[i].y) swap(e[i].x,e[i].y);
	}
	cin>>s;
	
	for(int i=1;i<=m;i++) if(e[i].x==1)
	{
		int y=e[i].y;
		if(belong[y]) continue;//debug
		belong[y]=++scc;
		dfs(y);
	}
	
	ans=cnt=0;
	memset(link,false,sizeof(link));
	memset(D,-1,sizeof(D));//这里的D[x][y]表示最小生成树中有没有选D[x][y]这条边，有则为其边权 
	kruskal();
	
	for(int i=s-cnt;i>=1;i--)
	{
		int mx=0,nx,ny,nk;
		for(int j=1;j<=m;j++)
		{
			if(e[j].v || e[j].x!=1) continue;
			int fx,fy,fmx=-1;
			find(e[j].y,fx,fy,fmx);
			if(fmx-e[j].c>mx)
			{
				mx=fmx-e[j].c;
				nx=fx;ny=fy;nk=j;
			}
		}
		if(mx==0) break;
		ans-=mx;
		/*D[nx][ny]=-1;
		D[e[nk].x][e[nk].y]=e[nk].c;debug*/
		e[nk].v=true;
		D[nx][ny]=D[ny][nx]=-1;
		D[e[nk].x][e[nk].y]=D[e[nk].y][e[nk].x]=e[nk].c;
	}
	
	printf("Total miles driven: %d\n",ans);
	return 0;
}