include

include

include

include

include

include

using namespace std;

const int MAXN = 1005; const int MAXK = 11; const int MAX_MASK = (1 << MAXK);

int n, m, k; vector> adj[MAXN]; int fish_types[MAXN]; int dist[MAXN][MAX_MASK];

void dijkstra() { // Priority queue stores {distance, {node, fish_mask}} priority_queue>, vector>>, greater>>> pq;

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < (1 << k); ++j) {
        dist[i][j] = INT_MAX;
    }
}

// Start at center 1 with the fish available there.
dist[1][fish_types[1]] = 0;
pq.push({0, {1, fish_types[1]}});

while (!pq.empty()) {
    auto [current_dist, state] = pq.top();
    pq.pop();
    int u = state.first;
    int current_mask = state.second;

    if (current_dist > dist[u][current_mask]) {
        continue;
    }

    // Explore neighbors
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        int new_mask = current_mask | fish_types[v];
        int new_dist = current_dist + weight;

        if (new_dist < dist[v][new_mask]) {
            dist[v][new_mask] = new_dist;
            pq.push({new_dist, {v, new_mask}});
        }
    }
}

}

int main() { cin >> n >> m >> k;

// Read fish types for each center
for (int i = 1; i <= n; ++i) {
    int t;
    cin >> t;
    int mask = 0;
    for (int j = 0; j < t; ++j) {
        int fish_type;
        cin >> fish_type;
        mask |= (1 << (fish_type - 1));
    }
    fish_types[i] = mask;
}

// Read roads and build adjacency list
for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
}

dijkstra();

int full_mask = (1 << k) - 1;
int min_time = INT_MAX;

// Check pairs of paths for the two cats
for (int mask1 = 0; mask1 < (1 << k); ++mask1) {
    for (int mask2 = 0; mask2 < (1 << k); ++mask2) {
        if ((mask1 | mask2) == full_mask) {
            if (dist[n][mask1] != INT_MAX && dist[n][mask2] != INT_MAX) {
                min_time = min(min_time, max(dist[n][mask1], dist[n][mask2]));
            }
        }
    }
}

cout << min_time << endl;

return 0;

}