/*

k度限制MST:有一个点的度<=k的MST

poj 1639

要求1号点的度不超过k 求MST

我们先把1号点扔掉 跑MST

假设有sum个连通分支 然后把这sum个分支连到1上

就得到了一个sum度的MST

这里往上连的时候 我们连这个分支里 距离1最近的

然后我们在1上加一条边 (即加一个度)得到sum+1度的MST

这里加边的时候 1连出去的每一条边都试一遍 取最小

假设当前1连到了 i 因为原来是个树 这样一搞就形成一个环

我们现在要删去环里面最长边 来得到更小的ans

我么维护dp[x]代表x到1的路径上权值最大的边的信息

(不包含与1直接相连的边否则删去1的度减1 并不能得到sum+1度的MST)

关键就是维护这个dp[x]

每次找sum+i度的MST之前我们从1dp一遍维护到每个点的max(沿着sum+i-1度的MST)

在树上跑 复杂度就降下来了On可以搞完

方程是 dp[x]=max(dp[from],G[from][x])

当新填的边不比找到的max边大的时候停下

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<map>

#define maxn 110

using namespace std;

int n,m,k,num,G[maxn][maxn],vis[maxn][maxn],ans,mt[maxn],wh[maxn],sum,fa[maxn];

map<string,int>f;

struct node{

    int u,v,t;

}e[maxn*maxn],dp[maxn*maxn];

int cmp(const node &A,const node &B){

    return A.t<B.t;

}

void Add(int from,int to,int dis){

    num++;e[num].v=to;

    e[num].u=from;

    e[num].t=dis;

}

int find(int x){

    return x==fa[x]?x:fa[x]=find(fa[x]);

}

void Dfs(int now,int from){

    for(int i=;i<=n;i++){

        if(i==from)continue;

        if(vis[now][i]){

            if(dp[i].t!=-){

                if(dp[now].t<G[now][i]){

                    dp[i].t=G[now][i];

                    dp[i].u=now;dp[i].v=i;

                }

                else dp[i]=dp[now];

            }

            Dfs(i,now);

        }

    }

}

void Kur(){

    sort(e+,e++num,cmp);

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<=m;i++){

        if(e[i].u==||e[i].v==)continue;

        if(find(e[i].u)==find(e[i].v))continue;

        ans+=e[i].t;fa[find(e[i].u)]=find(e[i].v);

        vis[e[i].u][e[i].v]=vis[e[i].v][e[i].u]=;

    }

}

int main(){

    scanf("%d",&m);f["Park"]=++n;

    string A,B;int t;

    memset(G,-,sizeof(G));

    for(int i=;i<=m;i++){

        cin>>A>>B>>t;

        if(f[A]==)f[A]=++n;if(f[B]==)f[B]=++n;

        Add(f[A],f[B],t);

        if(G[f[A]][f[B]]==-)G[f[A]][f[B]]=G[f[B]][f[A]]=t;

        else G[f[A]][f[B]]=G[f[B]][f[A]]=min(t,G[f[A]][f[B]]);

    }

    scanf("%d",&k);

    Kur();memset(mt,/,sizeof(mt));

    for(int i=;i<=n;i++){

        if(G[][i]!=-){

            int r=find(i);

            if(G[][i]<mt[r]){

                mt[r]=G[][i];

                wh[r]=i;

            }

        }

    }

    for(int i=;i<=n;i++)

        if(mt[i]!=mt[]){

            sum++;ans+=G[][wh[i]];

            vis[][wh[i]]=vis[wh[i]][]=;

        }

    //得到最小sum度树

    for(int i=sum+;i<=k;i++){

        dp[].t=-;

        for(int j=;j<=n;j++){

            if(vis[][j])dp[i].t=-;

            else dp[i].t=;

        }

        Dfs(,-);

        int pos,mii=1e9;

        for(int j=;j<=n;j++){

            if(G[][j]==-)continue;

            if(mii>G[][j]-dp[j].t){

                pos=j;mii=G[][j]-dp[j].t;

            }

        }

        if(mii>=)break;

        vis[][pos]=vis[pos][]=;

        vis[dp[pos].u][dp[pos].v]=;

        vis[dp[pos].v][dp[pos].u]=;

        ans+=mii;

    }

    printf("Total miles driven: %d\n",ans);

    return ;

}