#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

// --- 定数 ---
constexpr int N = 47, R = 1000, M = 400, K = 25;
constexpr int INF = 1e9;
constexpr int MAX_TIME_SLOTS = 182;
constexpr int MAX_FLIGHTS = 2500;

struct Flight {
    int u, s, v, t;
};

// スロット(0~180)を "HH:MM" 形式の文字列に変換
string to_time_str(int t) {
    int h = 6 + t / 12;
    int m = (t % 12) * 5;
    char buf[10];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, m);
    return string(buf);
}

struct Input {
    array<int, N> x, y, w;
    array<int, M> a, s, b, t;
    bool valid_dist[N][N]{};
    long long weight[N][N]{};
    long long total_W = 0;
    int dur[N][N]{};

    Input() {
        int _;
        cin >> _ >> _;
        for (int i = 0; i < N; ++i) cin >> x[i] >> y[i] >> w[i];
        cin >> _;
        string s_str, t_str;
        for (int i = 0; i < M; ++i) {
            cin >> a[i] >> s_str >> b[i] >> t_str;
            --a[i]; --b[i];
            s[i] = (stoi(s_str.substr(0, 2)) - 6) * 12 + stoi(s_str.substr(3, 2)) / 5;
            t[i] = (stoi(t_str.substr(0, 2)) - 6) * 12 + stoi(t_str.substr(3, 2)) / 5;
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == j) continue;
                long long dx = x[i] - x[j];
                long long dy = y[i] - y[j];
                dur[i][j] = (int)ceil((60.0 * sqrt(dx * dx + dy * dy) / 800.0 + 40.0) / 5.0 - 1e-9);
                if (dx * dx + dy * dy >= (R * R) / 16) {
                    valid_dist[i][j] = true;
                    weight[i][j] = (long long)w[i] * w[j];
                    total_W += weight[i][j] * 21;
                }
            }
        }
    }
};

// 計算用の巨大配列を持つワークスペース（生配列にして動的確保とオーバーヘッドを削除）
struct MarginalGainWorkspace {
    int current_s_ci[N][N][21];
    long long edge_gain[N][N][MAX_TIME_SLOTS];
    long long dp[N][MAX_TIME_SLOTS];
    int nxt_v[N][MAX_TIME_SLOTS];
};

// O(N^2) に圧縮された超高速な compute_s_ci
void compute_s_ci(const Input& in, const vector<Flight>& flights, int s_ci[N][N][21]) {
    for (int u = 0; u < N; ++u)
        for (int dst = 0; dst < N; ++dst) 
            for (int t_idx = 0; t_idx < 21; ++t_idx)
                s_ci[u][dst][t_idx] = -INF;

    int head[MAX_TIME_SLOTS + 1];
    memset(head, -1, sizeof(head));
    int nxt[MAX_FLIGHTS];
    
    for (int i = 0; i < (int)flights.size(); ++i) {
        int s = flights[i].s;
        if (s >= 0 && s <= 180) {
            nxt[i] = head[s];
            head[s] = i;
        }
    }

    for (int dst = 0; dst < N; ++dst) {
        int min_arr[N];
        for (int i = 0; i < N; ++i) min_arr[i] = INF;
        
        int next_T_idx[N];
        for (int i = 0; i < N; ++i) next_T_idx[i] = 20;

        for (int t = 180; t >= 0; --t) {
            for (int e = head[t]; e != -1; e = nxt[e]) {
                int u = flights[e].u;
                int v = flights[e].v;
                int arr_t = flights[e].t;
                if (arr_t <= 180) {
                    int arr_time_at_v = (v == dst) ? arr_t : min_arr[v];
                    if (arr_time_at_v < min_arr[u]) {
                        min_arr[u] = arr_time_at_v;
                        if (u != dst && in.valid_dist[u][dst]) {
                            while (next_T_idx[u] >= 0) {
                                int T_target = 60 + next_T_idx[u] * 6;
                                if (min_arr[u] <= T_target) {
                                    s_ci[u][dst][next_T_idx[u]] = t;
                                    next_T_idx[u]--;
                                } else {
                                    break;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

struct RivalSchedule {
    int s_sq[N][N][21];
    RivalSchedule(const Input& in) {
        vector<Flight> r_flights;
        r_flights.reserve(M);
        for (int i = 0; i < M; ++i) r_flights.push_back({in.a[i], in.s[i], in.b[i], in.t[i]});
        compute_s_ci(in, r_flights, s_sq);
    }
};

// キャッシュ最適化された DP テーブルの構築
void build_dp(const Input& in, const RivalSchedule& rival, MarginalGainWorkspace& mg_ws) {
    memset(mg_ws.edge_gain, 0, sizeof(mg_ws.edge_gain));

    for (int u = 0; u < N; ++u) {
        for (int v = 0; v < N; ++v) {
            if (u == v) continue;
            int d = in.dur[u][v];
            long long* gain_uv = mg_ws.edge_gain[u][v]; 
            
            for (int dst = 0; dst < N; ++dst) {
                if (!in.valid_dist[u][dst]) continue;
                long long w = in.weight[u][dst];
                const int* r_u_dst = rival.s_sq[u][dst];
                const int* c_u_dst = mg_ws.current_s_ci[u][dst];
                const int* c_v_dst = mg_ws.current_s_ci[v][dst];
                
                for (int T_idx = 0; T_idx < 21; ++T_idx) {
                    int r_s = r_u_dst[T_idx];
                    int c_s = c_u_dst[T_idx];
                    if (c_s > r_s) continue;

                    int min_s = max(0, r_s + 1);
                    int max_t = (v == dst) ? (60 + T_idx * 6) : c_v_dst[T_idx];
                    if (max_t < 0) continue;
                    int max_s = min(180 - d, max_t - d);

                    if (min_s <= max_s) {
                        gain_uv[min_s] += w;
                        if (max_s + 1 <= 180) gain_uv[max_s + 1] -= w;
                    }
                }
            }
            
            long long current_val = 0;
            for (int s = 0; s <= 180; ++s) {
                current_val += gain_uv[s];
                gain_uv[s] = current_val;
            }
        }
    }

    memset(mg_ws.dp, 0, sizeof(mg_ws.dp));
    memset(mg_ws.nxt_v, -1, sizeof(mg_ws.nxt_v));

    for (int t = 180; t >= 0; --t) {
        for (int u = 0; u < N; ++u) {
            if (t + 1 <= 180) {
                mg_ws.dp[u][t] = mg_ws.dp[u][t + 1];
                mg_ws.nxt_v[u][t] = -1;
            }
            for (int v = 0; v < N; ++v) {
                if (u == v) continue;
                int t_next = t + in.dur[u][v];
                if (t_next <= 180) {
                    long long gain = mg_ws.edge_gain[u][v][t];
                    if (gain + mg_ws.dp[v][t_next] > mg_ws.dp[u][t]) {
                        mg_ws.dp[u][t] = gain + mg_ws.dp[v][t_next];
                        mg_ws.nxt_v[u][t] = v;
                    }
                }
            }
        }
    }
}

long long get_score(const Input& in, const RivalSchedule& rival, const int c_s[N][N][21]) {
    long long v_ci = 0;
    for (int u = 0; u < N; ++u) {
        for (int v = 0; v < N; ++v) {
            if (!in.valid_dist[u][v]) continue;
            long long w = in.weight[u][v];
            const int* r_arr = rival.s_sq[u][v];
            const int* c_arr = c_s[u][v];
            for (int t = 0; t < 21; ++t) {
                if (c_arr[t] > r_arr[t]) v_ci += w;
            }
        }
    }
    return (long long)(1000000.0 * (double)v_ci / in.total_W);
}

// ビームサーチで管理する「状態」
struct State {
    vector<vector<Flight>> current_paths; 
    vector<Flight> all_flights;           
    long long score;                      

    bool operator<(const State& other) const {
        return score > other.score; 
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Input in;
    // 巨大な配列はヒープ領域に確保する
    auto mg_ws = make_unique<MarginalGainWorkspace>();
    RivalSchedule rival(in);

    // ★ ビームサーチの設定
    const int BEAM_WIDTH = 6;  // 保持する状態数
    const int BRANCHES = 10;   // 各状態から展開する「開始都市の数」

    vector<State> beam;
    State init_state;
    init_state.score = 0;
    beam.push_back(init_state);

    for (int k = 0; k < K; ++k) {
        vector<State> next_beam;
        
        for (const auto& state : beam) {
            compute_s_ci(in, state.all_flights, mg_ws->current_s_ci);
            
            build_dp(in, rival, *mg_ws);
            
            vector<pair<long long, int>> start_cands;
            for (int u = 0; u < N; ++u) {
                // ★ 修正箇所：emplace_back を使用して std::pair 推論エラーを回避
                start_cands.emplace_back(mg_ws->dp[u][0], u);
            }
            sort(start_cands.rbegin(), start_cands.rend());
            
            for (int i = 0; i < min(N, BRANCHES); ++i) {
                int start_u = start_cands[i].second;
                
                vector<Flight> path;
                int curr_u = start_u, curr_t = 0;
                while (curr_t <= 180) {
                    int next_city = mg_ws->nxt_v[curr_u][curr_t];
                    if (next_city != -1) {
                        int d = in.dur[curr_u][next_city];
                        path.push_back({curr_u, curr_t, next_city, curr_t + d});
                        curr_u = next_city;
                        curr_t += d;
                    } else {
                        curr_t += 1;
                    }
                }
                
                State nstate = state;
                nstate.current_paths.push_back(path);
                for (const auto& f : path) {
                    nstate.all_flights.push_back(f);
                }
                
                compute_s_ci(in, nstate.all_flights, mg_ws->current_s_ci);
                nstate.score = get_score(in, rival, mg_ws->current_s_ci);
                
                next_beam.push_back(nstate);
            }
        }
        
        sort(next_beam.begin(), next_beam.end());
        
        beam.clear();
        for (const auto& s : next_beam) {
            if (beam.empty() || beam.back().score != s.score) {
                beam.push_back(s);
                if (beam.size() == BEAM_WIDTH) break;
            }
        }
    }

    const auto& best_state = beam.front();
    for (int k = 0; k < K; ++k) {
        cout << best_state.current_paths[k].size() << "\n";
        for (const auto& f : best_state.current_paths[k]) {
            cout << f.u + 1 << " " << to_time_str(f.s) << " " 
                 << f.v + 1 << " " << to_time_str(f.t) << "\n";
        }
    }

    return 0;
}