#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 1000 + 10;
const int INF = 1<<29;

vector<int>E[maxn], W[maxn];
vector<int>cc[maxn];
int g[maxn][maxn], g2[maxn][maxn];
bool vis[maxn];
bool used[maxn];
int park, ncc, Nc[maxn];
int S[maxn];

struct Edge {
int u, v, w;
bool operator < (const Edge & rhs) const {
return w < rhs.w;
}
};

struct DP {
int nmax, u, v;
}dp[100][1000];

int fa[maxn], np;

void get_cc(int u) {　// 找连通分量
vis[u] = true;
cc[ncc].push_back(u);
Nc[u] = ncc;
for( int i=0; i<E[u].size(); i++ ) {
int v = E[u][i];
if(v == park) continue;
if(vis[v]) continue;
get_cc(v);
}
}


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

int kruscal(int x) {　// 求某个连通分量的最小生成树
int no[maxn];
Edge e[maxn];
int ne = 0;
for( int i=0; i<cc[x].size(); i++ ) fa[i] = i;
for( int i=0; i<cc[x].size(); i++ ) {
fa[i] = i, no[i] = cc[x][i];
for( int j=i+1; j<cc[x].size(); j++ ) {
int u = cc[x][i], v = cc[x][j];
int w = g[u][v];
if(g[u][v] == -1) continue;
e[ne].u = i, e[ne].v = j, e[ne].w = w; ne++;
}
}
sort(e, e+ne);
int sum = 0;
int tn = cc[x].size();
for( int i=0; i<ne; i++ ) {
int u = e[i].u, v = e[i].v, w = e[i].w;
int xx = find(u), y = find(v);
if(xx != y) {
fa[xx] = y;
g2[cc[x][u]][cc[x][v]] = g2[cc[x][v]][cc[x][u]] = w;
//printf("g2[%d][%d] = %d\n", cc[x][u], cc[x][v], g2[cc[x][u]][cc[x][v]]);
sum += w;
tn--;
if(tn == 1) break;
}
}
//printf("sum =%d\n", sum);
return sum;
}

void find_dp(int u, int fa, int nx) {　// 求出那个 dp 数组
vis[u] = true;
for( int i=1; i<np; i++ ) {
if(g2[u][i] == -1) continue;
int v = i;
if(v == fa) continue;
if(vis[v]) continue;
if(dp[nx][u].nmax > g2[u][v]) {
dp[nx][v].nmax = dp[nx][u].nmax;
dp[nx][v].u = dp[nx][u].u;
dp[nx][v].v = dp[nx][u].v;
}
else {
dp[nx][v].nmax = g2[u][v];
dp[nx][v].u = u;
dp[nx][v].v = v;
}
find_dp(v, u, nx);
}
}

void getEdge(int m) {　// 根据输入的信息建图
map<string,int>M;
memset(g, -1, sizeof(g));
char lname[100], rname[100];
for( int i=0; i<=1000; i++ ) E[i].clear(), W[i].clear(), cc[i].clear();
for( int i=0; i<m; i++ ) {
int u, v, w;
scanf("%s%s%d", lname, rname, &w);
string s = lname;
if(M[s] == 0) { u = np; M[s] = np++; }
else u = M[s];
s = rname;
if(M[s] == 0) { v = np; M[s] = np++; }
else v = M[s];
if(strcmp(lname, "Park") == 0) park = u;
else if(strcmp(rname, "Park") == 0) park = v;
E[u].push_back(v);
W[u].push_back(w);
E[v].push_back(u);
W[v].push_back(w);
g[u][v] = g[v][u] = w;
//printf("u = %d v = %d w = %d\n", u, v, w);
}
}

int main() {
freopen("in", "r", stdin);
int m;
while(scanf("%d", &m) != EOF) {
np = 1;
getEdge(m);
int k;
scanf("%d", &k);
ncc = 0;
memset(vis, 0, sizeof(vis));
for( int i=1; i<np; i++ ) {
if(i == park) continue;
if(vis[i]) continue;
get_cc(i);
ncc++;
}
int sum = 0;
memset(used, 0, sizeof(used));
memset(dp, 0, sizeof(dp));
memset(g2, -1, sizeof(g2));
for( int i=0; i<ncc; i++ ) {
sum += kruscal(i);
int nmin = INF, mark;
for( int j=0; j<cc[i].size(); j++ ) {
int u = cc[i][j];
if(g[u][park] == -1) continue;
if(nmin > g[u][park]) {
nmin = g[u][park];
mark = u;
}
}
dp[i][mark].nmax = 0;
memset(vis, 0, sizeof(vis));
find_dp(mark, -1, i);
S[i] = mark;
used[mark] = true;
sum += nmin;
}
k -= ncc;
while(k--) {
int nmin = INF, mark, mu, mv;
for( int i=0; i<E[park].size(); i++ ) {
int v = E[park][i];
if(used[v]) continue;
int tmp = g[park][v] - dp[Nc[v]][v].nmax;
if(tmp < nmin) {
nmin = tmp;
mark = v;
mu = dp[Nc[v]][v].u, mv = dp[Nc[v]][v].v;
}
}
if(nmin >= 0) break;
sum += nmin;
used[mark] = true;
g2[mu][mv] = 0;
//for( int i=2; i<=8; i++ ) printf("%d ", dp[0][i].nmax);
memset(dp, 0, sizeof(dp));
for( int i=0; i<ncc; i++ ) {
memset(vis, 0, sizeof(vis));
find_dp(S[i], -1, i);
}
}
printf("Total miles driven: %d\n", sum);
}
return 0;
}