/*
 * File:     main.cpp
 * Author:   Hrayr [HarHro94]
 * Problem:
 * IDE:      Visual C++ 2012
 */
//#pragma comment(linker, "/STACK:66777216")
#define _CRT_SECURE_NO_WARNINGS
#include <functional>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <fstream>
#include <cassert>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using namespace std;

typedef long long LL;
typedef long double LD;
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

const int INF = 1000000000;
const int N = 30;

int n, m, c, G[N][N];
map<string, int> id;
set<string> S;
string na[N], nb[N];
int dist[N];

struct Edge
{
    int u, v, w;
    Edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) { }
    bool operator < (const Edge &o) const
    {
        return w < o.w;
    }
};
vector<Edge> edge;

struct DSU
{
    int size[N], par[N];

    void init()
    {
        for (int i = 0; i < N; ++i)
        {
            size[i] = 1;
            par[i] = i;
        }
    }

    int getpar(int u)
    {
        return u == par[u] ? u : par[u] = getpar(par[u]);
    }

    void unite(int u, int v, int w, int &cur)
    {
        int p = getpar(u);
        int q = getpar(v);
        if (p == q) return;
        cur += w;
        if (size[p] > size[q]) swap(p, q);
        size[q] += size[p];
        par[p] = q;
    }

} dsu;

int main()
{
#ifdef harhro94
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#endif

    cin >> m;
    for (int i = 0; i < m; ++i)
    {
        cin >> na[i] >> nb[i] >> dist[i];
        S.insert(na[i]);
        S.insert(nb[i]);
    }
    cin >> c;
    for (auto it = S.begin(); it != S.end(); ++it)
        id[*it] = n++;

    int park = id["Park"];
    for (int i = 0; i < m; ++i)
    {
        int u = id[na[i]];
        int v = id[nb[i]];
        edge.pb(Edge(u, v, dist[i]));
        if (G[u][v] == 0)
            G[u][v] = G[v][u] = dist[i];
        else
            G[u][v] = min(G[u][v], dist[i]),
                      G[v][u] = min(G[v][u], dist[i]);
    }
    sort(all(edge));
    vector<int> adj;
    for (int i = 0; i < n; ++i)
        if (i != park && G[i][park]) adj.pb(i);
    int nx = sz(adj);
    int ans = INF;
    for (int mask = 0; mask < (1 << nx); ++mask)
    {
        int cnt = 0;
        for (int j = 0; j < nx; ++j)
            if ((mask >> j) & 1) ++cnt;
        if (cnt > c) continue;
        dsu.init();
        int cur = 0;
        for (int j = 0; j < nx; ++j)
            if ((mask >> j) & 1) dsu.unite(park, adj[j], G[park][adj[j]], cur);
        for (int i = 0; i < m; ++i)
            if (edge[i].u != park && edge[i].v != park)
                dsu.unite(edge[i].u, edge[i].v, edge[i].w, cur);
        if (dsu.size[dsu.getpar(0)] == n)
            ans = min(ans, cur);
    }
    cout << "Total miles driven: " << ans << endl;

#ifdef harhro94
    cerr << fixed << setprecision(3) << "\nExecution time = " << clock() / 1000.0 << "s\n";
#endif
    return 0;
}