//{{{
#include<algorithm>
#include<cmath>
#include<deque>
#include<fstream>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<random>
#include<set>
#include<sstream>
#include<sys/time.h>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(printde) FUNC(printde4) FUNC(printdbe) FUNC(printdwe) FUNC(printdu);
#endif
template <class S, class T>
istream& operator >> (istream& in, pair<S, T>& p){ return in >> p.first >> p.second; }
template <template <class T, class = std::allocator<T>> class V, class E>
istream& operator >> (istream& in, V<E>& v){ for(auto& e : v){ in >> e; } return in; }
//}}}

#ifdef LOCAL
#define LIMIT 5.0
// #define LIMIT 20.0
#else
#define LIMIT 25.0
#endif

// mt19937 mt(3);
mt19937 mt;

// structs
struct Edge{
    int cost, from, dest;
    Edge(){ }
    Edge(int cost, int dest): cost(cost), from(-1), dest(dest){ }
    Edge(int cost, int from, int dest): cost(cost), from(from), dest(dest){ }
    // bool operator == (const Edge& e) const { return cost == e.cost; }
    // bool operator < (const Edge& e) const { return cost < e.cost; }
    // bool operator == (const Edge& e) const { return from == e.from && dest == e.dest; }
    ostream& operator >> (ostream& out) const {
        return out << '(' << cost << ':' << from << ' ' << dest << ')';
    }
};
struct Graph{
    struct Node{
        vector<Edge> edges;
    };
    vector<Node> nodes;
    Graph(int num): nodes(num){ }
    int id(Node* n){ return n - &nodes[0]; }
    int id(Node& n){ return &n - &nodes[0]; }
    // // void print(){ for(auto& node : nodes){ prints(id(node), node.outEdges); } }
    void add1Edge(int from, int dest, int cost = 1){
        nodes[from].edges.emplace_back(cost, dest);
    }
    void add2Edge2(int from, int dest, int cost = 1){
        add1Edge(from, dest, cost);
        add1Edge(dest, from, cost);
    }
    void dfs(int idx, int from = -1){
        for(auto e : nodes[idx].edges){
            if(e.dest == from){ continue; }
            dfs(e.dest, idx);
        }
    }
};

struct Info {
    int id, dest;
    friend istream& operator >> (istream& in, Info& e){
        in >> e.id >> e.dest;
        e.dest--;
        return in;
    }
};

//TODO
// add 0 when tsp, remove after 0
// more test

// constants
int problem = 1;
int n, m;
vector<int> fs;
int tMax;
vector<Info> infos;
int lens[400][400];
vector<int> routes[400][400];
vector<Edge> edges;
vector<int> orderedTime;

// variables
int maxScore;

#define ALL_VARIABLES_DECLARATION\
    vector<int> dests;

#define ALL_VARIABLES_PARAMETER\
    vector<int>& dests

#define ALL_VARIABLES_ARGUMENT\
    dests

template <class... T>
void ignoreUnused(T&&...){ }

// {{{
struct Counter{
#ifdef LOCAL
#define COUNTER(name) Counter name(#name);
    int cnt = 0;
    string name;
    Counter(string name): name(name){ }
    ~Counter(){ printde(name, cnt); }
    void operator ++ (int){ cnt++; }
    void operator += (int d){ cnt += d; }
#else
#define COUNTER(name) Counter name;
    void operator ++ (int){ }
    void operator += (int){ }
#endif
};
// }}}
// COUNTER(cnt)
// COUNTER(trial)
// COUNTER(accepted)

// {{{
struct Watch {
    double prev;
    double getPrev(){
        return prev;
    }
#ifdef LOCAL
    timeval start;
    Watch(){
        gettimeofday(&start, nullptr);
    }
    double elapsed(){
        timeval now;
        gettimeofday(&now, nullptr);
        return prev = (now.tv_sec - start.tv_sec) + (now.tv_usec - start.tv_usec) / 1e6;
    }
#else
    double start;
#define ticks_per_sec 2800000000.0
    Watch(){
        start = get_time();
    }
    double elapsed(){
        return prev = get_time() - start;
    }
private:
    double get_time(){
        uint32_t lo, hi;
        asm volatile ("rdtsc" : "=a" (lo), "=d" (hi));
        return (((uint64_t)hi << 32) | lo) / ticks_per_sec;
    }
#endif
} watch;
// }}}

int traverseBF(ALL_VARIABLES_PARAMETER, unordered_map<int, int>& orders){
    // vector<int> os(orders.begin(), orders.end());
    vector<int> os;
    for(auto& o : orders){
        os.push_back(o.first);
    }
    auto os1 = os;
    sort(os.begin(), os.end());
    int mini = M;
    do{
        int cand = 0, pos = 0;
        for(auto& o : os){
            cand += lens[pos][o];
            pos = o;
        }
        cand += lens[pos][0];
        if(cand < mini){
            mini = cand;
            os1 = os;
        }
    }while(next_permutation(os.begin(), os.end()));
    os1.push_back(0);
    dests.insert(dests.end(), os1.begin(), os1.end());
    orders.clear();
    return mini;
}

int traverseGreedy(ALL_VARIABLES_PARAMETER, unordered_map<int, int>& orders){
    int pos = 0, ret = 0;
    int num = orders.size();
    for(int i = 0; i < num; i++){
        int order = 0, mini = M;
        for(auto& p : orders){
            int o = p.first;
            int len = lens[pos][o];
            if(len < mini){
                mini = len;
                order = o;
            }
        }
        ret += mini;
        pos = order;
        orders.erase(order);
        dests.push_back(order);
    }
    ret += lens[pos][0];
    orders.clear();
    dests.push_back(0);
    return ret;
}

int traverse2opt0(ALL_VARIABLES_PARAMETER, unordered_map<int, int>& orders, int t0){
    vector<pair<int, int>> os;
    {
        int pos = 0, ret = 0;
        int num = orders.size();
        for(int i = 0; i < num; i++){
            int mini = M;
            pair<int, int> order(0, 0);
            for(auto& p : orders){
                int o = p.first;
                int len = lens[pos][o];
                if(len < mini){
                    mini = len;
                    order = p;
                }
            }
            ret += mini;
            pos = order.first;
            orders.erase(order.first);
            os.push_back(order);
        }
        // os.push_back(0);
    }

    auto os1 = os;
    auto calc = [&](){ 
        int ret = 0, pos = 0;
        int t = t0;
        int over = 0;
        for(auto& p : os){
            int o = p.first;
            t += lens[pos][o];
            // ret += (t - orderedTime[o]) * (t - orderedTime[o]);
            // printde(t, orderedTime[o]);
            ret += lens[pos][o];
            pos = o;
            over += (t > tMax) * p.second;
        }
        t += lens[pos][0];
        ret += lens[pos][0];
        ret += over * 10000;
        return ret;
    };
    int mini = calc();
    // int m1 = mini;
    double limit = 1;
    // double limit = 0.1;
    if(mini > 10000){
        limit = LIMIT - watch.elapsed();
    }
    Watch watch;
    while(watch.elapsed() < limit){
        int i1 = mt() % (os.size() - 1), i2 = mt() % (os.size() - i1 - 1) + i1 + 1;
        if(i1 == 0 && os[i2].first == 0){
            continue;
        }
        for(int i = 0; i1 + i < i2 - i; i++){
            swap(os[i1 + i], os[i2 - i]);
        }
        int cand = calc();
        if(cand < mini){
            mini = cand;
            os1 = os;
        }else{
            for(int i = 0; i1 + i < i2 - i; i++){
                swap(os[i1 + i], os[i2 - i]);
            }
        }
    }
    int ret = 0, pos = 0;
    double coef = 0.01, base = 0;
    // double coef = 0.1, base = 0;
    for(size_t i = 0; i < os1.size(); i++){
        auto& o = os1[i].first;
        if((o && lens[o][0] < ret * coef + base && mini < 10000) || (t0 < 9400 && t0 + ret >= 9500)){
        // if(!o && i + 1 < os1.size()){
        // }
            while(i < os1.size()){
                orders[os1[i].first]++;
                i++;
            }
            dests.push_back(0);
            break;
        }
        ret += lens[pos][o];
        pos = o;
        dests.push_back(o);
    }
    dests.push_back(0);
    // printde(mini, ret, os1);
    return ret;
    // dests.insert(dests.end(), os1.begin(), os1.end());
    // printde(m1, mini);
    // return mini;
}
int traverse(ALL_VARIABLES_PARAMETER, unordered_map<int, int>& orders, int t0 = -1){
    // printde(orders.size());
    if(orders.size() < 12){
        return traverseBF(ALL_VARIABLES_ARGUMENT, orders);
    }
    if(watch.elapsed() < 25){
        return traverse2opt0(ALL_VARIABLES_ARGUMENT, orders, t0);
    }else{
        return traverseGreedy(ALL_VARIABLES_ARGUMENT, orders);
    }
}

void makeInit(ALL_VARIABLES_PARAMETER){
    unordered_map<int, int> orders;
    // int cnt = 0, cnt2 = 0;
    for(int i = 0; i < tMax; i++){
        if(infos[i].id != -1){
            // cnt2++;
            // cnt += orders.count(infos[i].dest);
            orders[infos[i].dest]++;
        }
        if(orders.empty()){ continue; }
        //TODO take infos into account even for B
        int t = traverse(ALL_VARIABLES_ARGUMENT, orders, i);
        // printde(orders.size());
        for(int j = 0; j < t - 1; j++){
            i++;
            if(i < tMax && infos[i].id != -1){
                // cnt2++;
                // cnt += orders.count(infos[i].dest);
                orders[infos[i].dest]++;
            }
        }
    }
    // printde(cnt, cnt2);
}

// void sa(ALL_VARIABLES_PARAMETER){
// }

void solve(ALL_VARIABLES_PARAMETER){
    makeInit(ALL_VARIABLES_ARGUMENT);
    // sa(ALL_VARIABLES_ARGUMENT);
}

// ----------------------------------------------------------------------

void solveB(ALL_VARIABLES_PARAMETER){
    unordered_map<int, int> orders;
    int cnt = 0;
    for(int i = 0; i <= tMax; ){
        auto input = [&](){ 
            if(i == tMax){
                exit(0);
            }
            i++;
            int nNew; cin >> nNew;
            if(nNew){
                Info info; cin >> info;
                orders[info.dest]++;
                orderedTime[info.dest] = i;
            }
            int nPut; cin >> nPut;
            for(int i = 0; i < nPut; i++){
                int id; cin >> id;
            }
            // printde(i, nNew, nPut);
            cerr.flush();
        };

        if(!i){
            input();
        }
        int t = 0;
        if(orders.size()){
            t = traverse(ALL_VARIABLES_ARGUMENT, orders);
            // for(int j = 0; j < t - 1; j++){
            //     i++;
            //     if(i < tMax && info.id != -1){
            //         orders.insert(info.dest);
            //     }
            // }
        }

        auto procResult = [&](){ 
            string s; cin >> s;
            if(s == "NG"){
                exit(0);
            }
            int n; cin >> n;
            for(int i = 0; i < n; i++){
                int id; cin >> id;
            }
        };
        if(dests.size()){
            int pos = 0;
            for(auto& dest : dests){
                if(dest < 0){
                    for(int i = 0; i < -dest; i++){
                        if(cnt == tMax){
                            printde("over tMax");
                            return;
                        }
                        cnt++;
                        cout << -1 << endl;
                        procResult();
                        input();
                    }
                }else{
                    for(auto& route : routes[pos][dest]){
                        // printde(t, i, dests);
                        for(int i = 0; i < lens[pos][route]; i++){
                            if(cnt == tMax){
                                printde("over tMax");
                                return;
                            }
                            cnt++;
                            cout << route + 1 << endl;
                            // printde(route + 1);
                            procResult();
                            input();
                        }
                        pos = route;
                    }
                }
            }
            dests.clear();
        }else{
            cnt++;
            cout << -1 << endl;
            procResult();
            input();
        }
    }
}

// ----------------------------------------------------------------------

void input(ALL_VARIABLES_PARAMETER){
    ignoreUnused(dests);
    cin >> n >> m;
    orderedTime.resize(n);
    Graph g(n);
    for(int i = 0; i < m; i++){
        int a, b, d;
        cin >> a >> b >> d;
        a--; b--;
        g.add2Edge2(a, b, d);
        edges.emplace_back(d, a, b);
        edges.emplace_back(d, b, a);
    }
    cin >> tMax;
    if(tMax != 10000){
        problem = 2;
        fs.resize(n);
        fs[0] = tMax;
        for(int i = 1; i < n; i++){
            cin >> fs[i];
        }
        cin >> tMax;
    }else{
        infos.resize(tMax);
        // int cnt = 0;
        for(int i = 0; i < tMax; i++){
            int n; cin >> n;
            if(n){
                // cnt++;
                cin >> infos[i];
                //TODO id
                orderedTime[infos[i].dest] = i;
            }else{
                infos[i].id = -1;
            }
        }
        // printde(cnt);
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            lens[i][j] = M;
        }
        lens[i][i] = 0;
    }
    for(auto& edge : edges){
        lens[edge.from][edge.dest] = edge.cost;
        routes[edge.from][edge.dest].push_back(edge.dest);
    }
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(lens[i][j] > lens[i][k] + lens[k][j]){
                    lens[i][j] = lens[i][k] + lens[k][j];
                    routes[i][j].clear();
                    routes[i][j].insert(routes[i][j].end(), routes[i][k].begin(), routes[i][k].end());
                    routes[i][j].insert(routes[i][j].end(), routes[k][j].begin(), routes[k][j].end());
                }
            }
        }
    }
}

void output(ALL_VARIABLES_PARAMETER){
    int pos = 0;
    // printde(dests);
    int cnt = 0;
    int visited = 0;
    printde(dests.size());
    for(auto& dest : dests){
        if(dest < 0){
            for(int i = 0; i < -dest; i++){
                if(cnt == tMax){
                    printde("over tMax", visited);
                    return;
                }
                cnt++;
                cout << -1 << '\n';
            }
        }else{
            // printde(routes[pos][dest]);
            for(auto& route : routes[pos][dest]){
                for(int i = 0; i < lens[pos][route]; i++){
                    if(cnt == tMax){
                        printde("over tMax", visited);
                        return;
                    }
                    cnt++;
                    cout << route + 1 << '\n';
                }
                pos = route;
            }
            visited++;
        }
    }
    while(cnt < tMax){
        cnt++;
        cout << -1 << '\n';
    }
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    ALL_VARIABLES_DECLARATION;
    input(ALL_VARIABLES_ARGUMENT);

    if(problem == 1){
        solve(ALL_VARIABLES_ARGUMENT);
        output(ALL_VARIABLES_ARGUMENT);
    }else{
        solveB(ALL_VARIABLES_ARGUMENT);
    }
}


Measured memory_bytes: 29312