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

constexpr int INF = INT_MAX;
constexpr int MAX_T = 10000;
constexpr int ROOT = 0;

array<double, 2605> exp_table;

chrono::system_clock::time_point START_TIME, END_TIME;

// int allBestTourLen;
// vector<int> allBestTour;

struct Order{
    int id, dst, time;
    Order(){}
    Order(int id, int dst, int time):id(id),dst(dst),time(time){}
};

struct Edge{
    int from, to, d;
    Edge(){}
    Edge(int from, int to, int d):from(from),to(to),d(d){}
};

struct Graph{
    int V;
    vector<vector<Edge> > g;
    vector<vector<int> > dist;
    vector<bool> onTour;
    vector<vector<int> > orderIds;
    vector<int> orderOldestTime;
    array<Order, MAX_T> orderList; 
    queue<int> orderQue;
    void init(int _V){
        V = _V;
        g.resize(V);
        onTour.resize(V);
        orderIds.resize(V);
        orderOldestTime.resize(V, INF);
    }
    void add_edge(int u, int v, int d){
        g[u].push_back(Edge(u,v,d));
        g[v].push_back(Edge(v,u,d));
    }
    void add_order(int id, int dst, int time){
        orderList[id] = Order(id,dst,time);
        orderQue.push(id);
    }
    bool receive_order(){
        if(orderQue.empty()) return false;
        while(!orderQue.empty()){
            int id = orderQue.front();
            int dst = orderList[id].dst;
            orderIds[dst].emplace_back(id);
            orderOldestTime[dst] = min(orderOldestTime[dst], orderList[id].time);
            orderQue.pop();
        }
        return true;
    }
    int count_order(int v){
        return orderIds[v].size();
    }
    int oldest_order_time(int v){
        return orderOldestTime[v];
    }
    void clear_order(int v){
        orderIds[v].clear();
        orderOldestTime[v] = INF;
    }
    void wf(){
        dist.resize(V, vector<int>(V, INF/3));
        for(auto &v : g){
            for(auto &e : v){
                int u = e.from, v = e.to, d = e.d;
                dist[u][v] = d;
                dist[v][u] = d;
            }
        }
        for(int i=0;i<V;i++){
            dist[i][i] = 0;
        }
        for(int k=0;k<V;k++){
            for(int i=0;i<V;i++){
                for(int j=0;j<V;j++){
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
    }
    vector<Edge> operator [](int i) {
        return g[i];
    }
};

struct Vehicle{
    int from, to;
    int cnt;
    bool onNode, onRoot;
    void init(){
        from = ROOT;
        to = -1;
        cnt = 0;
        onNode = true;
        onRoot = true;
    }
    void move(){
        if(to == -1) return;
        if(cnt > 0){
            cnt--;
            onNode = false;
            onRoot = false;
        }
        if(cnt == 0){
            from = to;
            to = -1;
            onNode = true;
            onRoot = from == ROOT;
        }
    }
};

double randFloat(double r){
    return double(rand())/RAND_MAX*r;
}

int calc_tour_len(const vector<int> &tour, Graph &graph){
    int len = 0, n = tour.size();
    for(int i=0;i<n-1;i++){
        len += graph.dist[tour[i]][tour[i+1]];
    }
    if(n > 0) len += graph.dist[ROOT][tour[0]] + graph.dist[tour[n-1]][ROOT];
    return len;
}

void rev_insert(vector<int> &a, vector<int> &b, int l, int r){
    for(int i=r-1;i>=l;i--){
        a.emplace_back(b[i]);
    }
}

void Two_Opt(vector<int> &tour, Graph &graph, const int maxLoop = 1000){
    vector<int> besttour = tour;
    int dif = 0, dmin = 0;

    for(int loopCount = 0; loopCount < maxLoop; loopCount++){
        for(int i=0;i<int(tour.size())-2;i++){
            for(int j=i+1;j<int(tour.size())-1;j++){
                int lhs = graph.dist[tour[i]][tour[i+1]] + graph.dist[tour[j]][tour[j+1]];
                int rhs = graph.dist[tour[i]][tour[j]] + graph.dist[tour[i+1]][tour[j+1]];
                if(lhs > rhs || exp_table[min(100,rhs-lhs)*13] > randFloat(1.0)){
                    dif += rhs-lhs; 
                    reverse(tour.begin()+i+1, tour.begin()+j+1);
                    if(dif < dmin){
                        dmin = dif;
                        besttour = tour;
                    }
                }
            }
        }
    }
    tour = besttour;
}

void Three_Opt(vector<int> &tour, Graph &graph, const int maxLoop = 3){
    vector<int> besttour = tour;
    int n = tour.size();
    int dif = 0, dmin = 0;
    vector<int> newtour;
    bool update = false;
    int t = -1;
    for(int loopcount = 0; loopcount < 3; loopcount++){
        for(int i=0;i<n-3;i++){
            for(int j=i+1;j<n-2;j++){
                for(int k=j+1;k<n-1;k++){
                    int d[5], mini = 0;
                    d[0] = graph.dist[tour[i]][tour[i+1]] + graph.dist[tour[j]][tour[j+1]] + graph.dist[tour[k]][tour[k+1]];
                    d[1] = graph.dist[tour[i]][tour[k]] + graph.dist[tour[j+1]][tour[i+1]] + graph.dist[tour[k+1]][tour[j]];
                    d[2] = graph.dist[tour[j+1]][tour[i]] + graph.dist[tour[k]][tour[j]] + graph.dist[tour[k+1]][tour[i+1]];
                    d[3] = graph.dist[tour[j]][tour[k+1]] + graph.dist[tour[i]][tour[j+1]] + graph.dist[tour[k]][tour[i+1]];
                    d[4] = graph.dist[tour[i]][tour[j]] + graph.dist[tour[j+1]][tour[k+1]] + graph.dist[tour[k]][tour[i+1]];
                    for(int m = 1; m <= 4; m++){
                        if(d[m] < d[mini]) mini = m;
                    }
                    if(mini == 0) continue;

                    newtour.clear();
                    newtour.insert(newtour.end(),tour.begin(),tour.begin()+i+1);
                    if (mini == 1){
                        rev_insert(newtour,tour,j+1,k+1);
                        newtour.insert(newtour.end(),tour.begin()+i+1,tour.begin()+j+1);
                    } else if (mini == 2){
                        newtour.insert(newtour.end(),tour.begin()+j+1,tour.begin()+k+1);
                        rev_insert(newtour,tour,i+1,j+1);
                    } else if (mini == 3){
                        newtour.insert(newtour.end(),tour.begin()+j+1,tour.begin()+k+1);
                        newtour.insert(newtour.end(),tour.begin()+i+1,tour.begin()+j+1);
                    } else if (mini == 4){
                        rev_insert(newtour,tour,i+1,j+1);
                        rev_insert(newtour,tour,j+1,k+1);
                    }
                    newtour.insert(newtour.end(),tour.begin()+k+1,tour.end());
                    tour = newtour;

                    dif += d[mini] - d[0];
                    if(dif < dmin){
                        dmin = dif;
                        besttour = tour;
                        update = true;
                        t = loopcount;
                    }
                }
            }
        }
    }
    tour = besttour;
}

vector<int> build_path(Graph &graph, const int tlim){

    // vector<int> ls;
    // for(int i=0;i<graph.V;i++){
    //     if(graph.count_order(i) > 0 && !graph.onTour[i]){
    //         ls.emplace_back(i);
    //     }
    // }

    vector<pair<int,int> > ordls;
    for(int i=1;i<graph.V;i++){
        if(graph.count_order(i) > 0 && !graph.onTour[i]){
            ordls.emplace_back(make_pair(graph.oldest_order_time(i),i));
        }
    }
    sort(ordls.begin(), ordls.end());

    vector<int> tour = {ROOT, ROOT};
    vector<bool> used(graph.V,false);
    int t = 0;
    for(int i=0;i<int(ordls.size());i++){
        int id = ordls[i].second;
        int dif = INF, k = -1;
        for(int j=0;j<int(tour.size())-1;j++){
            int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
            if(d < dif){
                dif = d;
                k = j+1;
            }
        }
        if(t + dif <= tlim){
            t += dif;
            used[i] = true;
            tour.insert(tour.begin() + k, id);
        }
    }
    if(tour.size() == 2){
        return {};
    }

    // tour.push_back(0);
    // for(int i=0;i<int(ls.size());i++){
    //     int dmin = INF, k = -1;
    //     for(int j : ls){
    //         if(used[j]) continue;
    //         if(dmin > graph.dist[tour.back()][j]){
    //             dmin = graph.dist[tour.back()][j];
    //             k = j;
    //         }
    //     }
    //     tour.emplace_back(k);
    //     used[k] = true;
    // }
    // tour.emplace_back(0);
    
    for(int s=0;s<2;s++){
        Two_Opt(tour, graph);
        // Three_Opt(tour, graph);
        t = calc_tour_len(tour, graph);
        for(int i=0;i<int(ordls.size());i++){
            int id = ordls[i].second;
            int dif = INF, k = -1;
            for(int j=0;j<int(tour.size())-1;j++){
                int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
                if(d < dif){
                    dif = d;
                    k = j+1;
                }
            }
            if(t + dif <= tlim){
                t += dif;
                used[i] = true;
                tour.insert(tour.begin() + k, id);
            }
        }
    }

    tour.erase(tour.begin());
    tour.pop_back();
    return tour;
}

vector<int> build_last_path(Graph &graph, int tlim){
    vector<pair<int,int> > ordls;
    for(int i=1;i<graph.V;i++){
        if(graph.count_order(i) > 0){
            ordls.emplace_back(make_pair(graph.count_order(i),i));
        }
    }
    sort(ordls.rbegin(), ordls.rend());

    int t = 0, n = ordls.size();
    int cnt = 0, bestcnt = 0, besttime = INF;
    vector<int> tour, besttour;
    vector<bool> used(n);
    tour.emplace_back(ROOT);
    for(int i=0;i<n;i++){
        int id = ordls[i].second;
        int dif = INF, k = -1;
        for(int j=0;j<int(tour.size())-1;j++){
            int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
            if(d < dif){
                dif = d;
                k = j+1;
            }
        }
        if(graph.dist[tour.back()][id] < dif){
            dif = graph.dist[tour.back()][id];
            k = tour.size();
        }
        if(t + dif <= tlim){
            t += dif;
            cnt += ordls[i].first;
            used[i] = true;
            tour.insert(tour.begin() + k, id);
        }
    }
    if(tour.size() == 1){
        return {};
    }
    bestcnt = cnt;
    besttime = t;
    besttour = tour;

    for(int s = 0; s < 9; s++){
        for(int loopCount = 0; loopCount < 1800; loopCount++){
            for(int i=0;i<int(tour.size())-1;i++){
                for(int j=i+1;j<int(tour.size());j++){
                    int lhs = graph.dist[tour[i]][tour[i+1]] + (j+1<int(tour.size()) ? graph.dist[tour[j]][tour[j+1]] : 0);
                    int rhs = graph.dist[tour[i]][tour[j]] + (j+1<int(tour.size()) ? graph.dist[tour[i+1]][tour[j+1]] : 0);
                    if(t + rhs - lhs > tlim) continue;
                    if(lhs > rhs || exp_table[min(200,rhs-lhs)*12] > randFloat(1.0)){
                        t += rhs-lhs; 
                        reverse(tour.begin()+i+1, tour.begin()+j+1);
                        if(t < besttime){
                            besttime = t;
                            besttour = tour;
                        }
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            if(used[i]) continue;
            if(s < 4 && ordls[i].first < 3) break;
            int id = ordls[i].second;
            int dif = INF, k = -1;
            for(int j=0;j<int(tour.size())-1;j++){
                int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
                if(d < dif){
                    dif = d;
                    k = j+1;
                }
            }
            if(graph.dist[tour.back()][id] < dif){
                dif = graph.dist[tour.back()][id];
                k = tour.size();
            }
            if(t + dif <= tlim){
                t += dif;
                cnt += ordls[i].first;
                used[i] = true;
                tour.insert(tour.begin() + k, id);
                if(cnt > bestcnt){
                    besttour = tour;
                    besttime = t;
                    bestcnt = cnt;
                }
            }
        }
    }
    besttour.erase(besttour.begin());
    return besttour;
}

vector<int> build_path2(Graph &graph, int tlim){
    vector<pair<int,int> > ordls;
    for(int i=1;i<graph.V;i++){
        if(graph.count_order(i) > 0 && !graph.onTour[i]){
            ordls.emplace_back(make_pair(graph.oldest_order_time(i),i));
        }
    }
    sort(ordls.begin(), ordls.end());

    int t = 0, n = ordls.size();
    int cnt = 0, bestcnt = 0, besttime = INF;
    vector<int> tour, besttour;
    vector<bool> used(n);
    tour.emplace_back(ROOT);
    tour.emplace_back(ROOT);
    for(int i=0;i<n;i++){
        int id = ordls[i].second;
        int dif = INF, k = -1;
        for(int j=0;j<int(tour.size())-1;j++){
            int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
            if(d < dif){
                dif = d;
                k = j+1;
            }
        }
        if(t + dif <= tlim){
            t += dif;
            cnt += ordls[i].first;
            used[i] = true;
            tour.insert(tour.begin() + k, id);
        }
    }
    if(tour.size() == 1){
        return {};
    }
    bestcnt = cnt;
    besttime = t;
    besttour = tour;

    for(int s = 0; s < 6; s++){
        for(int loopCount = 0; loopCount < 1200; loopCount++){
            for(int i=0;i<int(tour.size())-2;i++){
                for(int j=i+1;j<int(tour.size())-1;j++){
                    int lhs = graph.dist[tour[i]][tour[i+1]] + (j+1<int(tour.size()) ? graph.dist[tour[j]][tour[j+1]] : 0);
                    int rhs = graph.dist[tour[i]][tour[j]] + (j+1<int(tour.size()) ? graph.dist[tour[i+1]][tour[j+1]] : 0);
                    if(t + rhs - lhs > tlim) continue;
                    if(lhs > rhs || exp_table[min(rhs-lhs,200)*14] > randFloat(1.0)){
                        t += rhs-lhs; 
                        reverse(tour.begin()+i+1, tour.begin()+j+1);
                        if(t < besttime){
                            besttime = t;
                            besttour = tour;
                        }
                    }
                }
            }
        }
        for(int i=0;i<n;i++){
            if(used[i]) continue;
            int id = ordls[i].second;
            int dif = INF, k = -1;
            for(int j=0;j<int(tour.size())-1;j++){
                int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
                if(d < dif){
                    dif = d;
                    k = j+1;
                }
            }
            if(t + dif <= tlim){
                t += dif;
                cnt += ordls[i].first;
                used[i] = true;
                tour.insert(tour.begin() + k, id);
                if(cnt > bestcnt){
                    besttour = tour;
                    besttime = t;
                    bestcnt = cnt;
                }
            }
        }
    }
    besttour.erase(besttour.begin());
    return besttour;
}

int main(void){
    cin.tie(0);
   	ios::sync_with_stdio(false);
    START_TIME = chrono::system_clock::now();
    int V, E, Tmax;
    cin >> V >> E;
    Graph graph;
    graph.init(V);
    for(int i=0;i<E;i++){
        int u, v, d;
        cin >> u >> v >> d;
        u--; v--;
        graph.add_edge(u,v,d);
    }

    vector<int> f(V);
    for(int i=0;i<V;i++){
        cin >> f[i];
    }

    cin >> Tmax;

    graph.wf();
    for(int i=0;i<=2600;i++){
        exp_table[i] = exp(-0.1*i);
    }

    Vehicle vehicle;
    vehicle.init();
    queue<int> tourQue;
    bool flag = false;

    for(int t=0;t<Tmax;t++){
        // 情報の受け取り
        int n;
        cin >> n;
        for(int i=0;i<n;i++){
            int id, dst;
            cin >> id >> dst;
            dst--;
            graph.add_order(id, dst, t);
        }
        cin >> n;
        for(int i=0;i<n;i++){
            int id;
            cin >> id;
        }

        if(t == 9200) flag = true;

        bool turnEnd = false;
        if(vehicle.onRoot){
            if(graph.receive_order()){
                vector<int> nxtTour;
                if(t < 8000) nxtTour = build_path2(graph, (flag?INF:V*2));
                else nxtTour = build_last_path(graph, (flag?INF:V*2));
                int dt = calc_tour_len(nxtTour, graph);
                if(t + dt < Tmax){
                    for(auto &v : nxtTour){
                        tourQue.push(v);
                        graph.onTour[v] = true;
                    }
                }
                else{
                    nxtTour = build_last_path(graph, Tmax - t);
                    while(!tourQue.empty()) tourQue.pop();
                    for(auto &v : nxtTour){
                        tourQue.push(v);
                        graph.onTour[v] = true;
                    }
                }
            }
            flag = false;
            if(tourQue.empty()){
                cout << -1 << "\n";
                turnEnd = true;
            }
        }

        if(!turnEnd){
            if(vehicle.onNode){
                int dst;
                while(!tourQue.empty()){
                    int v = tourQue.front();
                    if(graph.count_order(v) == 0) tourQue.pop();
                    else break;
                }
                if(tourQue.empty() || flag){
                    dst = ROOT;
                }else{
                    dst = tourQue.front();
                }
                for(auto &e : graph[vehicle.from]){
                    if(vehicle.from == e.to) continue;
                    if(graph.dist[vehicle.from][e.to] + graph.dist[e.to][dst] == graph.dist[vehicle.from][dst] && graph.dist[vehicle.from][e.to] == e.d){
                        vehicle.to = e.to;
                        vehicle.cnt = e.d;
                        break;
                    }
                }
            }
            if(vehicle.to != -1){
                cout << vehicle.to + 1 << "\n";
                vehicle.move();
            }
            else cout << -1 << "\n";
            if(vehicle.onNode){
                graph.clear_order(vehicle.from);
                graph.onTour[vehicle.from] = false;
            }
        }
        cout << flush;

        string verdict;
        cin >> verdict;
        if(verdict == "NG"){
            return 0;
        }
        cin >> n;
        for(int i=0;i<n;i++){
            int id = 0;
            cin >> id;
        }
    }
    END_TIME = chrono::system_clock::now();
    // cout << double(chrono::duration_cast<chrono::milliseconds>(END_TIME-START_TIME).count()) << "ms" << endl;
    return 0;
}

Measured memory_bytes: 2004