#include <bits/stdc++.h>
using namespace std;
# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

using ll = long long;
const int DAY_START = 6*60;   // 360
const int DAY_END   = 21*60;  // 1260
const int INF_NEG = -1000000000;

struct City { double x, y; ll w; };

struct Flight {
    int a; // 1-based city
    int dep; // minutes
    int b;
    int arr; // minutes
};

int flight_duration_min(const City &c1, const City &c2) {
    double dx = c1.x - c2.x;
    double dy = c1.y - c2.y;
    double d = sqrt(dx*dx + dy*dy);
    double raw = 60.0 * d / 800.0 + 40.0;
    int dur = (int)ceil(raw / 5.0) * 5;
    return dur;
}

string time_to_str(int m) {
    int h = m/60, mm = m%60;
    char buf[6];
    snprintf(buf, sizeof(buf), "%02d:%02d", h, mm);
    return string(buf);
}

// Remove consecutive duplicate cities from a sequence
vector<int> compress_sequence(const vector<int>& seq) {
    vector<int> out;
    out.reserve(seq.size());
    for (size_t i = 0; i < seq.size(); ++i) {
        if (i == 0 || seq[i] != seq[i-1]) out.push_back(seq[i]);
    }
    return out;
}

// Compute dp given flights sorted in descending departure order
vector<int> compute_dp_from_flights(int N, const vector<Flight>& flights_desc_dep, int v, int t) {
    vector<int> dp(N+1, INF_NEG);
    dp[v] = t;
    for (const auto &f : flights_desc_dep) {
        if (dp[f.b] >= f.arr) {
            if (f.dep > dp[f.a]) dp[f.a] = f.dep;
        }
    }
    return dp;
}

// Precompute dp for square flights for all (v,ti)
void precompute_square_dp(int N, const vector<Flight>& square_flights, const vector<int>& target_times,
                          vector<vector<int>>& dp_square_by_target) {
    vector<Flight> desc = square_flights;
    sort(desc.begin(), desc.end(), [](const Flight& A, const Flight& B){
        return A.dep > B.dep;
    });
    dp_square_by_target.clear();
    dp_square_by_target.reserve(N * (int)target_times.size());
    for (int v = 1; v <= N; ++v) {
        for (size_t ti = 0; ti < target_times.size(); ++ti) {
            int t = target_times[ti];
            vector<int> dp = compute_dp_from_flights(N, desc, v, t);
            dp_square_by_target.push_back(std::move(dp));
        }
    }
}

// Build flights (circle) from sequences: each sequence is vector<int> cities visited in order.
// Start time = DAY_START at seq[0], flights between consecutive cities. Stop if arrival > DAY_END.
// Skip legs where a == b (shouldn't occur if sequences are compressed).
vector<Flight> build_circle_flights_from_seqs(const vector<vector<int>>& seqs, const vector<City>& cities) {
    vector<Flight> res;
    for (const auto &raw_seq : seqs) {
        if (raw_seq.size() < 2) continue;
        vector<int> seq = compress_sequence(raw_seq);
        int cur_time = DAY_START;
        for (size_t i = 0; i + 1 < seq.size(); ++i) {
            int a = seq[i];
            int b = seq[i+1];
            if (a == b) continue;
            if (a < 1 || a > (int)cities.size() || b < 1 || b > (int)cities.size()) continue;
            int dur = flight_duration_min(cities[a-1], cities[b-1]);
            int depart = cur_time;
            int arrive = depart + dur;
            if (arrive > DAY_END) break;
            res.push_back({a, depart, b, arrive});
            cur_time = arrive;
            if (cur_time >= DAY_END) break;
        }
    }
    return res;
}

// Compute score S for given circle_flights and precomputed square dp.
// Uses dp propagation per (v,ti).
long double compute_score_S(int N, const vector<City>& cities, const vector<Flight>& square_flights,
                            const vector<vector<int>>& dp_square_by_target, const vector<int>& target_times,
                            const vector<Flight>& circle_flights) {
    vector<Flight> desc = circle_flights;
    sort(desc.begin(), desc.end(), [](const Flight& A, const Flight& B){
        return A.dep > B.dep;
    });

    long double v_circle = 0.0L;
    long double v_square = 0.0L;

    int T = (int)target_times.size();
    for (int v = 1; v <= N; ++v) {
        for (int ti = 0; ti < T; ++ti) {
            int idx = (v-1)*T + ti;
            // dp for circle flights
            vector<int> dp_circle = compute_dp_from_flights(N, desc, v, target_times[ti]);
            const vector<int>& dp_square = dp_square_by_target[idx];
            for (int i = 1; i <= N; ++i) {
                if (i == v) continue;
                long double prod = (long double)cities[i-1].w * (long double)cities[v-1].w;
                int dc = dp_circle[i];
                int ds = dp_square[i];
                if (dc <= INF_NEG/2 && ds <= INF_NEG/2) continue;
                if (dc >= ds) v_circle += prod;
                else v_square += prod;
            }
        }
    }
    long double S = 0.0L;
    long double denom = v_circle + v_square;
    if (denom > 0) S = v_circle / denom;
    return S;
}

// Extend a single sequence by adding cities (population-weighted) while time remains.
// seq is assumed to be compressed already (but we compress inside to be safe).
vector<int> extend_sequence_by_time(const vector<int>& raw_seq, const vector<City>& cities,
                                    const vector<double>& pop_weights, std::mt19937_64 &rng) {
    vector<int> seq = compress_sequence(raw_seq);
    if (seq.empty()) return seq;
    // compute cur_time by simulating existing legs
    int cur_time = DAY_START;
    for (size_t i = 0; i + 1 < seq.size(); ++i) {
        int a = seq[i];
        int b = seq[i+1];
        if (a < 1 || a > (int)cities.size() || b < 1 || b > (int)cities.size()) { cur_time = DAY_END + 1; break; }
        if (a == b) continue;
        int dur = flight_duration_min(cities[a-1], cities[b-1]);
        int arrive = cur_time + dur;
        if (arrive > DAY_END) { // truncate at this point
            seq.resize(i+1);
            cur_time = DAY_END + 1;
            break;
        }
        cur_time = arrive;
        if (cur_time >= DAY_END) break;
    }
    if (cur_time > DAY_END) {
        // truncated to beyond day end => just compress and return
        return compress_sequence(seq);
    }
    int cur_city = seq.back();
    // keep adding while we can
    while (cur_time < DAY_END) {
        // build weights excluding current city
        vector<double> weights = pop_weights;
        if (cur_city >= 1 && cur_city <= (int)weights.size()) weights[cur_city-1] = 0.0;
        double total_w = 0.0;
        for (double w : weights) total_w += w;
        if (total_w <= 0.0) break;
        discrete_distribution<int> d(weights.begin(), weights.end());
        int next_city = d(rng) + 1;
        if (next_city == cur_city) {
            // extremely unlikely due to weight zero, but guard
            break;
        }
        int dur = flight_duration_min(cities[cur_city-1], cities[next_city-1]);
        int arrive = cur_time + dur;
        if (arrive > DAY_END) break;
        seq.push_back(next_city);
        cur_time = arrive;
        cur_city = next_city;
    }
    return compress_sequence(seq);
}

// Clamp sequences by time (truncate legs that would exceed DAY_END), compress duplicates,
// and then extend sequences to fill remaining time by adding cities weighted by population.
// Requires pop_weights and rng for extension behavior.
vector<vector<int>> clamp_and_extend_sequences_by_time(const vector<vector<int>>& seqs, const vector<City>& cities,
                                                       const vector<double>& pop_weights, std::mt19937_64 &rng) {
    vector<vector<int>> out;
    out.reserve(seqs.size());
    for (const auto &raw : seqs) {
        // first compress & truncate legs that exceed day end
        vector<int> seq = compress_sequence(raw);
        vector<int> cur;
        if (seq.empty()) { out.push_back(cur); continue; }
        cur.push_back(seq[0]);
        int cur_time = DAY_START;
        for (size_t i = 0; i + 1 < seq.size(); ++i) {
            int a = seq[i];
            int b = seq[i+1];
            if (a == b) continue;
            if (a <1 || a > (int)cities.size() || b <1 || b >(int)cities.size()) break;
            int dur = flight_duration_min(cities[a-1], cities[b-1]);
            int arrive = cur_time + dur;
            if (arrive > DAY_END) break;
            cur.push_back(b);
            cur_time = arrive;
            if (cur_time >= DAY_END) break;
        }
        // now extend using randomness and weights
        vector<int> extended = extend_sequence_by_time(cur, cities, pop_weights, rng);
        out.push_back(compress_sequence(extended));
    }
    return out;
}

// --- NEW: neighbor selection biased toward short distances ---
// choose a city index (1-based) preferring cities near prev and/or next.
// prev and next may be 0 if not present. dist is NxN matrix (0-based indices).
int choose_city_nearby(int N, int prev, int next, const vector<double>& pop_weights,
                       const vector<vector<double>>& dist, mt19937_64 &rng) {
    vector<double> weights(N, 0.0);
    double eps = 1e-9;
    for (int j = 0; j < N; ++j) {
        // skip selecting identical to prev or next to reduce trivial duplicates
        if ((prev>0 && j+1 == prev) || (next>0 && j+1 == next)) {
            weights[j] = 0.0;
            continue;
        }
        double pop = pop_weights[j];
        double wprev = 1.0;
        double wnext = 1.0;
        if (prev > 0) {
            double d = dist[prev-1][j];
            wprev = 1.0 / (1.0 + d); // nearer -> larger
        }
        if (next > 0) {
            double d = dist[j][next-1];
            wnext = 1.0 / (1.0 + d);
        }
        // combine contributions; if both prev and next exist, sum them
        double w = pop * (wprev + wnext);
        weights[j] = w + eps; // ensure non-zero small floor
    }
    // Create discrete distribution from weights
    discrete_distribution<int> dd(weights.begin(), weights.end());
    int idx = dd(rng); // 0-based index
    return idx + 1; // return 1-based city id
}

// neighbor_modify_sequence: uses nearby-biased chooser
void neighbor_modify_sequence_nearby(vector<int>& seq, const vector<double>& pop_weights,
                                     const vector<vector<double>>& dist, mt19937_64 &rng) {
    int n = (int)seq.size();
    int op = (int)(rng() % 3); // insert, delete, replace
    if (op == 0) { // insert
        int pos = n == 0 ? 0 : (int)(rng() % (uint64_t)(n + 1));
        int prev = (pos == 0 ? 0 : seq[pos-1]);
        int next = (pos == n ? 0 : seq[pos]);
        int c = choose_city_nearby((int)pop_weights.size(), prev, next, pop_weights, dist, rng);
        seq.insert(seq.begin() + pos, c);
    } else if (op == 1) { // delete
        if (n == 0) {
            // fallback to insert
            int pos = 0;
            int prev = 0, next = 0;
            int c = choose_city_nearby((int)pop_weights.size(), prev, next, pop_weights, dist, rng);
            seq.push_back(c);
        } else {
            int pos = (int)(rng() % (uint64_t)n);
            seq.erase(seq.begin() + pos);
        }
    } else { // replace
        if (n == 0) {
            int prev = 0, next = 0;
            int c = choose_city_nearby((int)pop_weights.size(), prev, next, pop_weights, dist, rng);
            seq.push_back(c);
        } else {
            int pos = (int)(rng() % (uint64_t)n);
            int prev = (pos == 0 ? 0 : seq[pos-1]);
            int next = (pos+1 >= n ? 0 : seq[pos+1]);
            int c = choose_city_nearby((int)pop_weights.size(), prev, next, pop_weights, dist, rng);
            seq[pos] = c;
        }
    }
    seq = compress_sequence(seq);
}

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

    auto t_start = chrono::high_resolution_clock::now();

    int N; int R;
    if (!(cin >> N >> R)) return 0;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) {
        double x,y; ll w;
        cin >> x >> y >> w;
        cities[i] = {x,y,w};
    }
    // precompute distance matrix (Euclidean)
    vector<vector<double>> dist(N, vector<double>(N, 0.0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            double dx = cities[i].x - cities[j].x;
            double dy = cities[i].y - cities[j].y;
            dist[i][j] = sqrt(dx*dx + dy*dy);
        }
    }

    int M; cin >> M;
    vector<Flight> square_flights;
    for (int i = 0; i < M; ++i) {
        int a, b; string s_str, t_str;
        cin >> a >> s_str >> b >> t_str;
        int s = stoi(s_str.substr(0,2))*60 + stoi(s_str.substr(3,2));
        int tt = stoi(t_str.substr(0,2))*60 + stoi(t_str.substr(3,2));
        square_flights.push_back({a, s, b, tt});
    }
    int K; cin >> K;

    // Target times: 11:00,11:30,...,21:00 (21 times)
    vector<int> target_times;
    for (int h = 11; h <= 21; ++h) {
        target_times.push_back(h*60 + 0);
        if (h != 21) target_times.push_back(h*60 + 30);
    }
    int T = (int)target_times.size();

    vector<vector<int>> dp_square_by_target;
    precompute_square_dp(N, square_flights, target_times, dp_square_by_target);

    mt19937_64 rng(42);

    vector<double> pop_weights(N);
    for (int i = 0; i < N; ++i) pop_weights[i] = (double)cities[i].w;

    // initial sequences
    vector<vector<int>> seqs(K);
    discrete_distribution<int> start_dist(pop_weights.begin(), pop_weights.end());
    uniform_int_distribution<int> len_dist(1, max(1, N/4));
    for (int p = 0; p < K; ++p) {
        int len = len_dist(rng);
        vector<int> seq;
        seq.reserve(len);
        int first = start_dist(rng) + 1;
        seq.push_back(first);
        for (int j = 1; j < len; ++j) {
            discrete_distribution<int> d(pop_weights.begin(), pop_weights.end());
            int c = d(rng) + 1;
            seq.push_back(c);
        }
        seqs[p] = compress_sequence(seq);
    }

    // clamp and extend initial sequences
    seqs = clamp_and_extend_sequences_by_time(seqs, cities, pop_weights, rng);

    vector<Flight> circle_flights = build_circle_flights_from_seqs(seqs, cities);
    long double best_score = compute_score_S(N, cities, square_flights, dp_square_by_target, target_times, circle_flights);
    vector<vector<int>> best_seqs = seqs;
    long double cur_score = best_score;

    double T0 = 1.0, T_end = 1e-7;
    int iterations = 0, score_evals = 1;

    const double TIME_LIMIT_SEC = 0.99;
    while (true) {
        auto now = chrono::high_resolution_clock::now();
        double elapsed = chrono::duration_cast<chrono::duration<double>>(now - t_start).count();
        if (elapsed >= TIME_LIMIT_SEC) break;
        double frac = elapsed / TIME_LIMIT_SEC;
        double temp = T0 * pow(T_end / T0, frac);

        int p = (int)(rng() % (uint64_t)max(1, K));
        vector<int> new_seq = seqs[p];

        // use nearby-biased neighbor modifier
        neighbor_modify_sequence_nearby(new_seq, pop_weights, dist, rng);

        // compress candidate sequence (already done in neighbor func)
        // new_seq = compress_sequence(new_seq);

        vector<vector<int>> cand_seqs = seqs;
        cand_seqs[p] = new_seq;
        // clamp & extend candidate sequences (this may add extra legs if time remains)
        cand_seqs = clamp_and_extend_sequences_by_time(cand_seqs, cities, pop_weights, rng);
        vector<Flight> cand_circle_flights = build_circle_flights_from_seqs(cand_seqs, cities);
        long double cand_score = compute_score_S(N, cities, square_flights, dp_square_by_target, target_times, cand_circle_flights);
        score_evals++;

        long double delta = cand_score - cur_score;
        bool accept = false;
        if (delta >= 0) accept = true;
        else {
            double prob = exp((double)(delta) / max(1e-12, temp));
            double r = (double)(rng() % 1000000) / 1000000.0;
            if (r < prob) accept = true;
        }
        if (accept) {
            seqs = std::move(cand_seqs);
            circle_flights = std::move(cand_circle_flights);
            cur_score = cand_score;
            if (cur_score > best_score) {
                best_score = cur_score;
                best_seqs = seqs;
            }
        }
        iterations++;
    }

    // Final: clamp & extend best_seqs (to ensure final output uses extension)
    vector<vector<int>> final_seqs = clamp_and_extend_sequences_by_time(best_seqs, cities, pop_weights, rng);

    // Output per-plane flights
    for (int p = 0; p < K; ++p) {
        const auto &seq = final_seqs[p];
        vector<pair<pair<int,int>, pair<int,int>>> flights_print;
        if (!seq.empty()) {
            int cur_time = DAY_START;
            for (size_t i = 0; i + 1 < seq.size(); ++i) {
                int a = seq[i];
                int b = seq[i+1];
                if (a == b) continue; // safety
                int dur = flight_duration_min(cities[a-1], cities[b-1]);
                int depart = cur_time;
                int arrive = depart + dur;
                if (arrive > DAY_END) break;
                flights_print.push_back({{a, depart}, {b, arrive}});
                cur_time = arrive;
                if (cur_time >= DAY_END) break;
            }
        }
        cout << flights_print.size() << "\n";
        for (auto &fp : flights_print) {
            int a = fp.first.first;
            int dep = fp.first.second;
            int b = fp.second.first;
            int arr = fp.second.second;
            cout << a << " " << time_to_str(dep) << " " << b << " " << time_to_str(arr) << "\n";
        }
    }
    cout.flush();

    auto t_end = chrono::high_resolution_clock::now();
    auto elapsed_ms = chrono::duration_cast<chrono::milliseconds>(t_end - t_start).count();
    cerr << "elapsed_ms: " << elapsed_ms << "\n";
    cerr << "iterations: " << iterations << "\n";
    cerr << "score_evals: " << score_evals << "\n";
    cerr << "best_S: " << std::fixed << std::setprecision(9) << (double)best_score << "\n";
    cerr.flush();

    return 0;
}