#include <bits/stdc++.h>
using namespace std;

const int N = 25, inf = 0x3f3f3f3f;

int g[N][N], dist[N];
int tr[N][N], pre[N]; // tr最小生成树的矩阵，pre[y] = x: (x - > y) tr[y][pre[y]];
int n, m, ans, s, deg;
int f[N], fx[N], fy[N]; // 以某个点为子树的树边的最大值为f[i], 这条边连接的点为(fx[i], fy[i])
bool v[N], c[N];
vector<int> con;
unordered_map<string, int> h;

int get(string x) {
    if(!h[x]) h[x] = ++ n;
    return h[x];
}

void prim() { // 求最小生成树
    dist[con[0]] = 0;
    for(int i = 0; i < con.size(); i ++ ) {
        int x = 0;
        for(int j = 0; j < con.size(); j ++ ) 
            if(!v[con[j]] && (x == 0 || dist[x] > dist[con[j]])) x = con[j];
        v[x] = true;
        ans += dist[x];
        for(int y = 0; y < con.size(); y ++ ) 
            if(!v[con[y]] && dist[con[y]] > g[x][con[y]]) dist[con[y]] = g[x][con[y]], pre[con[y]] = x;
    }
    int mini = con[0];
    for(int i = 1; i < con.size(); i ++ ) {
        int x = con[i];
        tr[pre[x]][x] = tr[x][pre[x]] = dist[x];
        if(g[1][mini] > g[1][x]) mini = x;
    }
    deg ++ ;
    ans += g[1][mini];
    tr[1][mini] = tr[mini][1] = g[1][mini];
}

void dfs(int x) {
    c[x] = true;
    con.push_back(x);
    for(int i = 2; i <= n; i ++ ) 
        if(!c[i] && g[x][i] < 0x3f3f3f3f) dfs(i);
}

void con_prim() {
    memset(tr, 0x3f, sizeof tr);
    memset(dist, 0x3f, sizeof dist);
    c[1] = true;
    for(int i = 2; i <= n; i ++ ) {
        if(!c[i]) {
            con.clear();
            dfs(i);
            prim();
        }
    }
}

void dp(int x) {
    c[x] = true;
    for(int y = 1; y <= n; y ++ ) 
        if(!c[y] && tr[x][y] < inf) {
            if(tr[x][y] < f[x]) {
                f[y] = f[x];
                fx[y] = fx[x], fy[y] = fy[x];
            }
            else {
                f[y] = tr[x][y];
                fx[y] = x, fy[y] = y;
            }
            dp(y);
        }
    c[x] = false;
}

bool solve() { //  删除输边，加非树边的操作
    int min_edge = inf, mini;
    for(int i = 2; i <= n; i ++ ) {
        if(tr[1][i] < 0x3f3f3f3f || g[1][i] == inf) continue;
        if(g[1][i] - f[i] < inf && min_edge > g[1][i] - f[i]) {
            min_edge = g[1][i] - f[i];
            mini = i;
        }
    }
    if(min_edge >= 0) return false;
    ans += min_edge;
    deg ++ ;
    tr[1][mini] = tr[mini][1] = g[1][mini];
    tr[fx[mini]][fy[mini]] = tr[fy[mini]][fx[mini]] = inf;
    f[mini] = g[1][mini];
    fx[mini] = 1, fy[mini] = mini;
    dp(mini);
    return true;
}

int main() {
    cin >> m;
    get("Park");
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++ ) {
        int x, y, z;
        string a, b;
        cin >> a >> b >> z;
        x = get(a), y = get(b);
        g[x][y] = g[y][x] = min(g[x][y], z);
    }
    cin >> s;
    con_prim(); // O(n ^ 2)
    memset(c, 0, sizeof c);
    dp(1); // 以某个点为根的子树的树边的最大值
    while(deg < s) { // O(n ^ 4)
        if(!solve()) break;
    }
    cout << "Total miles driven: " << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 25, inf = 0x3f3f3f3f;

int g[N][N], dist[N];
int tr[N][N], pre[N]; // tr最小生成树的矩阵，pre[y] = x: (x - > y) tr[y][pre[y]];
int n, m, ans, s, deg;
bool v[N];
unordered_map<string, int> h;

int get(string x) {
    if(!h[x]) h[x] = ++ n;
    return h[x];
}

void prim() { // 求最小生成树
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n; i ++ ) {
        int x = 0;
        for(int j = 1; j <= n; j ++ ) 
            if(!v[j] && (x == 0 || dist[x] > dist[j])) x = j;
        v[x] = true;
        ans += dist[x];
        for(int y = 1; y <= n; y ++ ) 
            if(!v[y] && dist[y] > g[x][y]) dist[y] = g[x][y], pre[y] = x;
    }
    memset(tr, 0x3f, sizeof tr);
    for(int x = 1; x <= n; x ++ ) {
        if(pre[x] == 1) deg ++ ;
        tr[pre[x]][x] = tr[x][pre[x]] = dist[x];
    }
}

void dfs(int x) {
    v[x] = true;
    for(int i = 2; i <= n; i ++ ) 
        if(!v[i] && tr[x][i] < 0x3f3f3f3f) dfs(i);
}

int find_min(int &x, int &y) { // 找最小边
    int min_edge = 0x3f3f3f3f;
    for(int i = 2; i <= n; i ++ ) if(!v[i])
        for(int j = 2; j <= n; j ++ ) if(v[j]) 
            if(min_edge > g[i][j]) {
                min_edge = g[i][j];
                x = i, y = j;
            }
    return min_edge;
}

void solve() { //  删除输边，加非树边的操作
    int min_edge = inf, minx, miny, mini;
    for(int i = 2; i <= n; i ++ ) {
        if(tr[1][i] == 0x3f3f3f3f) continue;
        memset(v, 0, sizeof v);
        v[1] = true;
        dfs(i);
        int x, y;
        int add_edge = find_min(x, y);
        if(add_edge < inf && min_edge > add_edge - tr[1][i]) {
            minx = x, miny = y, mini = i;
            min_edge = add_edge - tr[1][i];
        }
    }
    ans += min_edge;
    deg -- ;
    tr[1][mini] = tr[mini][1] = inf;
    tr[minx][miny] = tr[miny][minx] = g[minx][miny];
}

int main() {
    cin >> m;
    get("Park");
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i < m; i ++ ) {
        int x, y, z;
        string a, b;
        cin >> a >> b >> z;
        x = get(a), y = get(b);
        g[x][y] = g[y][x] = min(g[x][y], z);
    }
    cin >> s;
    prim();
    while(deg > s) {
        solve();
    }
    cout << "Total miles driven: " << ans << endl;
    return 0;
}