#include<iostream>
#include<cstring>
using namespace std;
const int INF=10000000;

int edge[25][25],visit[25];
int cost[25][25],point[25];
int ax,ay,k,cnt,largest;

void Input()
{
         int x,y,i,j,n,dist;
         char name[22][12],name1[12],name2[12];
         for(i=0;i<25;i++) {
              for(j=0;j<25;j++) {
                  edge[i][j]=0;
                  cost[i][j]=INF;
               }
          }
         strcpy(name[0],"Park");
         cnt=1;
         cin>>n;
         for(i=0;i<n;i++)
         {
                cin>>name1>>name2>>dist;
                for(j=0;j<cnt;j++)
                {
                        if(strcmp(name[j],name1)==0) { x=j; break; }
                }
                if(j>=cnt)
                {
                        strcpy(name[cnt],name1);
                        x=cnt;cnt++;
                }
                for(j=0;j<cnt;j++)
                {
                         if(strcmp(name[j],name2)==0) {y=j; break;  }
                }
                if(j>=cnt)
                {
                         strcpy(name[cnt],name2);
                         y=cnt;cnt++;
                }
                if(cost[x][y]>dist)
                         cost[x][y]=cost[y][x]=dist;
         }
         cin>>k;
}

void dfs(int ver,int count)
{

         if(ver==0)
         {
                for(int i=1;i<count;i++)
                {
                       if(cost[point[i]][point[i-1]]>largest)
                       {
                              ax=point[i];ay=point[i-1];
                              largest=cost[ax][ay];
                       }
                }
                return;
         }
         for(int i=0;i<cnt;i++)
         {
                if(!visit[i]&&edge[ver][i])
                {

                       visit[i]=1;
                       point[count]=ver;
                       dfs(i,count+1);
                       visit[i]=0;

                }
         }

}

int prim()
{
           int i,mn,min=0;
           int opt[22],pre[22];
           bool flag[22];
           for(i=1;i<cnt;i++)
           {
                  pre[i]=1;
                  flag[i]=false;
                  opt[i]=cost[1][i];
           }
           flag[1]=true;

           int ver,number=cnt-2;
           while(number--)
           {
                  mn=INF;
                  for(i=1;i<cnt;i++)
                  {
                         if(!flag[i]&&mn>opt[i])
                         {
                                mn=opt[i];ver=i;
                         }
                  }
                  if(mn==INF) break;
                  min+=mn;
                  flag[ver]=true;
                  edge[ver][pre[ver]]=1;
                  edge[pre[ver]][ver]=1;
                  for(i=1;i<cnt;i++)
                  {
                          if(!flag[i]&&opt[i]>cost[ver][i])
                          {
                                 opt[i]=cost[ver][i];
                                 pre[i]=ver;
                          }
                  }
           }

           return min;

}


void solve()
{
         int i,j,m,ver,min,mn;
         bool flag[22];
         min=prim();
         mn=INF;

         for(i=1;i<cnt;i++)
         {
                if(mn>cost[i][0])
                {
                       ver=i;mn=cost[i][0];
                }
         }

         min+=mn;
         edge[ver][0]=edge[0][ver]=1;

         for(i=2;i<=k&&i<=cnt;i++)
         {
                int p1=0,p2=0;
                int cmost=INF;
                ax=ay=0;
                for(j=1;j<cnt;j++)
                {
                        if(!edge[j][0]&&cost[j][0]<INF)
                        {
                                memset(visit,0,sizeof(visit));
                                memset(point,0,sizeof(point));
                                largest=0;
                                visit[j]=1;
                                dfs(j,0);
                                visit[j]=0;
                                if(cost[0][j]-cost[ax][ay]<cmost)
                                {
                                        cmost=cost[0][j]-cost[ax][ay];
                                        p1=ax;p2=ay;ver=j;
                                }
                        }
                }
                if(cmost<0) min+=cmost;
                else break;
                edge[0][ver]=edge[ver][0]=1;
                edge[p1][p2]=edge[p2][p1]=0;
         }
         cout<<"Total miles driven: "<<min<<endl;
}

int main()
{
         Input();
         solve();
         return(0);
}