#include <bits/stdc++.h>

using namespace std;

const int N=;

#define quick() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)//读入优化

#define mem(a,b) memset(a,b,sizeof(a))//初始化

#define init() mem(g,0),mem(vis,false),root=cnt=tot2=tot=0,q.clear(),q2.clear()//初始化大军

#define add(a,b,c) g[a][b]=g[b][a]=c//无向图加边

#define mk(a,b) make_pair(a,b)//简便

int tot2,tot,n,m,fa[N],cnt,c,s,root,g[][],dis[][];

//tot2为边的数量

//tot为点的数量

//cnt为编号的数量

map<string,int> q;//映射关系

map<pair<int,int>,bool> q2;//统计这条边是否出现在最小生成树中

int vis[N];//标记连通块的编号

string a,b;

int find(int x)

{

    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);//并查集找红太阳

}

struct edge1

{

    int x,y,w;

} g2[N];

int cmp (edge1 a,edge1 b)

{

    return a.w<b.w;//最小边排序

}

struct node

{

    int u,v,d;//(u,v)节点权值为d

    inline void inits()

    {

        u=v=;

        d=-;

    }

} dp[N];

struct edge2

{

    inline void add_edge(int a,int b,int c)//加入一条边

    {

        g2[++tot2].x=a;//起点

        g2[tot2].y=b;//终点

        g2[tot2].w=c;//权值

    }

    inline int kruskal()

    {

        sort(g2+,g2++tot2,cmp);//排序,找最小

        int ans=;//我们的目标连通块的连通块编号

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

        {

            int x=find(g2[i].x),y=find(g2[i].y);//求出所在连通块

            if (x== || y== || x==y)//不是目标连通块,或者已经在一起了

                continue;

            fa[x]=y;//合并

            ans+=g2[i].w;//统计

            q2[mk(g2[i].x,g2[i].y)]=true;//这条边出现过

            q2[mk(g2[i].y,g2[i].x)]=true;

        }

        return ans;

    }

} g3;

void read()

{

    quick();

    init();

    cin>>n;

    root=q["Park"]=tot=;//Park节点就是我们的一号节点

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

    {

        cin>>a>>b>>c;

        if (!q[a])//名字读入

            q[a]=(++tot);//新编号

        if (!q[b])

            q[b]=(++tot);//新编号

        g3.add_edge(q[a],q[b],c);//加边

        add(q[a],q[b],c);//加边

        fa[i]=i;//初始化每个点的父亲节点

    }

    cin>>s;

}

void dfs(int x)

{

    for(int j=; j<=tot; j++)

        if (g[x][j] && !vis[j])//有边,但是木有被标记

        {

            vis[j]=cnt;

            dfs(j);

        }

}

void pd()//连通块划分

{

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

        if (!vis[i])

        {

            cnt++;//又来一个

            vis[i]=cnt;

            dfs(i);

        }

}

void dfs(int now,int last)//计算(1,x)路径上最大边

{

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

    {

        if(i==last || !q2[mk(now,i)])//点重叠,或者没有这条边

            continue;

        if(dp[i].d==-)//没有来过

        {

            if(dp[now].d>g[now][i])

                dp[i]=dp[now];

            else

            {

                dp[i].u=now;

                dp[i].v=i;

                dp[i].d=g[now][i];

            }

        }

        dfs(i,now);

    }

}

void work()

{

    pd();

    int ans=g3.kruskal();//统计每一个连通块的值

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

    {

        int now=0x3f3f3f3f,st=;//初始值为INF

        for(int j=; j<=tot; j++)

            if (vis[j]==i)//属于这个连通块

                if (now>g[][j] && g[][j]!=)

                {

                    now=g[][j];//找到与1相连最小的边

                    st=j;

                }

        ans+=now;//将每一个连通块与1相连

        q2[mk(,st)]=q2[mk(st,)]=true;

    }

    int t=cnt;

    while(s>t)

    {

        s--;

        int now=,idx=;

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

            dp[i].inits();

        dfs(,-);//求每一个点到1的途中最大边是谁?

        for(int j=; j<=tot; j++)

        {

            if(now<dp[j].d-g[][j] && g[][j])

            {

                now=dp[j].d-g[][j];//找到最大权值边

                idx=j;

            }

        }

        if (now<=)//已经不会多优秀了

            break;

        ans=ans-now;

        q2[mk(dp[idx].u,dp[idx].v)]=false;//删除边

        q2[mk(,idx)]=q2[mk(idx,)]=true;//添加边

    }

    cout<<"Total miles driven: "<<ans;

}

int main()

{

    read();

    work();

    return ;

}