#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <queue>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

const ll CYCLE_PER_SEC = 2700000000;
const double TIME_LIMIT = 2.0;
ll startCycle;

unsigned long long xor128() {
    static unsigned long long rx = 123456789, ry = 362436069, rz = 521288629, rw = 88675123;
    unsigned long long rt = (rx ^ (rx << 11));
    rx = ry;
    ry = rz;
    rz = rw;
    return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}

unsigned long long int getCycle() {
    unsigned int low, high;
    __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
    return ((unsigned long long int) low) | ((unsigned long long int) high << 32);
}

double getTime(unsigned long long int begin_cycle) {
    return (double) (getCycle() - begin_cycle) / CYCLE_PER_SEC;
}

const int MAX_V = 401;
const int MAX_T = 10000;
const ll BASE_SCORE = pow(MAX_T, 2);
const int INF = 99999;

const int UNKNOWN = -1;
const int STORE_ID = 0;

const int WAIT_COMMAND = -1;

int V, E, T, orderCount;
int cost[MAX_V][MAX_V];
int penalty[MAX_T + 10];

void warshall_floyd(int v = MAX_V) {
    for (int k = 0; k < v; k++) {
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }
}

struct Edge {
    int from;
    int to;
    int dist;

    Edge(int from = -1, int to = -1, int dist = INF) {
        this->from = from;
        this->to = to;
        this->dist = dist;
    }
};

struct Vertex {
    int id;
    int packageCount;
    vector<int> deliver_times;
    vector <Edge> edges;

    Vertex(int id = -1) {
        this->id = id;
        this->packageCount = 0;
    }
};

struct Order {
    int id;
    int dest;

    Order(int id = -1, int dest = UNKNOWN) {
        this->id = id;
        this->dest = dest;
    }
};

struct PathInfo {
    int dist;
    vector<int> path;
};

struct Action {
    int dest;
    int waitCount;

    Action(int dest = -1, int waitCount = 0) {
        this->dest = dest;
        this->waitCount = waitCount;
    }
};

struct Node {
    int v;
    int dist;
    vector<int> path;

    Node(int v = -1, int dist = -1) {
        this->v = v;
        this->dist = dist;
    }

    bool operator>(const Node &n) const {
        return dist > n.dist;
    }
};

vector <Vertex> vertexList;
vector <Edge> edgeList;
Order orderTimeLine[MAX_T + 10];
vector <Order> orderList;
int nextOrderTime[MAX_T + 10];

class HokudaiHitachi {
public:
    void init() {
        for (int i = 0; i < MAX_V; ++i) {
            for (int j = 0; j < MAX_V; ++j) {
                if (i == j) {
                    cost[i][j] = 0;
                } else {
                    cost[i][j] = INF;
                }
            }
        }

        for (int t = MAX_T; t >= 0; --t) {
            nextOrderTime[t] = MAX_T;
            penalty[t] = pow(t, 2);
        }
    }

    vector <Action> initSolver() {
        vector <Action> result;

        if (orderTimeLine[0].dest != UNKNOWN) {
            result.push_back(Action(STORE_ID, 0));
        } else {
            result.push_back(Action(STORE_ID, 10));
        }

        for (int i = 0; i < orderCount; ++i) {
            Order *order = &orderList[i];
            assert(order->dest != UNKNOWN);
            result.push_back(Action(order->dest));

            if ((i + 1) % 20 == 0) {
                result.push_back(Action(STORE_ID, 0));
            }
        }

        return result;
    }

    vector<int> run() {
        vector <Action> result = buildDeliverPath();

        return actions2answer(result);
    }

    vector <Action> buildDeliverPath() {
        vector <Action> bestActions = initSolver();
        vector <Action> actions = bestActions;
        ll bestScore = calcScore(bestActions);
        ll currentScore = bestScore;

        double currentTime = getTime(startCycle);
        int tryCount = 0;

        while (currentTime < TIME_LIMIT) {
            currentTime = getTime(startCycle);

            int type = xor128() % 2;
            int len = actions.size();

            int i, j;

            do {
                i = xor128() % (len - 1) + 1;
                j = xor128() % (len - 1) + 1;
            } while (i == j);

            Action temp = actions[i];
            actions[i] = actions[j];
            actions[j] = temp;

            ll score = calcScore(actions);

            if (bestScore < score) {
                bestScore = score;
                bestActions = actions;
            } else {
                Action temp = actions[i];
                actions[i] = actions[j];
                actions[j] = temp;
            }

            ++tryCount;
        }

        fprintf(stderr, "tryCount = %d\n", tryCount);

        return bestActions;
    }

    vector<int> actions2answer(vector <Action> &actions) {
        int current = STORE_ID;
        int time = 0;
        vector<int> answer;

        for (int i = 0; i < actions.size() && time < MAX_T; ++i) {
            Action action = actions[i];
            int dest = action.dest;

            PathInfo pathInfo = getPath(current, dest);

            for (int j = 0; j < pathInfo.path.size(); ++j) {
                int to = pathInfo.path[j];
                int d = cost[current][to];

                assert(STORE_ID <= to && to <= V - 1);
                assert(d > 0);

                while (time < MAX_T && d > 0) {
                    answer.push_back(to + 1);
                    ++time;
                    --d;
                }

                current = to;
            }

            assert(current == dest);

            if (dest == STORE_ID) {
                int nextTime = time;

                for (int j = 0; j < action.waitCount; ++j) {
                    nextTime = nextOrderTime[nextTime];
                }

                for (int t = time; t < nextTime; ++t) {
                    answer.push_back(WAIT_COMMAND);
                }

                time = nextTime;
            }
        }

        while (answer.size() < MAX_T) {
            answer.push_back(WAIT_COMMAND);
        }

        return answer;
    }

    ll calcScore(vector <Action> &actions) {
        ll totalScore = 0;

        int time = 0;
        int current = STORE_ID;
        int updated_at = 0;
        int delivered_count[V];
        memset(delivered_count, 0, sizeof(delivered_count));
        vector<int> orders;

        for (int i = 0; i < actions.size() && time < MAX_T; ++i) {
            Action *action = &actions[i];
            int dest = action->dest;

            if (dest < 0 || V <= dest) {
                fprintf(stderr, "dest = %d\n", dest);
            }
            assert(STORE_ID <= current && current < V);
            assert(STORE_ID <= dest && dest < V);

            if (current == STORE_ID) {
                updated_at = time;
            } else {
                int cnt = delivered_count[current];

                while (cnt < vertexList[dest].packageCount && vertexList[dest].deliver_times[cnt] <= time) {
                    int delay = time - vertexList[dest].deliver_times[cnt];
                    assert(0 <= delay && delay <= MAX_T);
                    totalScore += BASE_SCORE - penalty[delay];
                    ++cnt;
                }

                delivered_count[current] = cnt;
            }

            if (current != dest) {
                current = dest;

                if (cost[current][dest] > MAX_T) {
                    fprintf(stderr, "%d -> %d cost %d\n", current, dest, cost[current][dest]);
                }

                assert(cost[current][dest] <= MAX_T);
                time += cost[current][dest];
            }

            if (dest == STORE_ID) {
                for (int j = 0; j < action->waitCount; ++j) {
                    time = nextOrderTime[time];
                }
            }

            if (time > MAX_T) {
                fprintf(stderr, "Invalid time %d\n", time);
            }
            assert(time <= MAX_T);
        }

        return totalScore;
    }

    PathInfo getPath(int from, int to) {
        PathInfo pathInfo;
        pathInfo.dist = 0;

        priority_queue <Node, vector<Node>, greater<Node>> pque;
        pque.push(Node(from, 0));

        bool visited[V];
        memset(visited, false, sizeof(visited));

        while (!pque.empty()) {
            Node node = pque.top();
            pque.pop();

            if (visited[node.v]) continue;
            visited[node.v] = true;

            if (node.v == to) {
                pathInfo.path = node.path;
                pathInfo.dist = node.dist;
                break;
            }

            for (int i = 0; i < vertexList[node.v].edges.size(); ++i) {
                Edge *edge = &vertexList[node.v].edges[i];

                assert(edge->from == node.v);

                Node next(edge->to, node.dist + edge->dist);
                next.path = node.path;
                next.path.push_back(edge->to);

                pque.push(next);
            }
        }

        return pathInfo;
    }
};

int main() {
    startCycle = getCycle();
    HokudaiHitachi hh;
    hh.init();
    cin >> V >> E;

    for (int vid = 0; vid < V; ++vid) {
        Vertex vertex(vid);

        vertexList.push_back(vertex);
    }

    int u, v, d;
    for (int i = 0; i < E; ++i) {
        cin >> u >> v >> d;

        --u;
        --v;

        cost[u][v] = d;
        cost[v][u] = d;

        Edge e1(u, v, d);
        Edge e2(v, u, d);

        edgeList.push_back(e1);

        vertexList[u].edges.push_back(e1);
        vertexList[v].edges.push_back(e2);
    }

    warshall_floyd(V);

    cin >> T;

    int N;
    int id, dst;
    orderCount = 0;

    for (int t = 0; t < T; ++t) {
        cin >> N;
        if (N == 0) continue;

        cin >> id >> dst;
        --dst;
        Order order(id, dst);
        orderTimeLine[t] = order;
        orderList.push_back(order);
        vertexList[dst].deliver_times.push_back(t);
        ++vertexList[dst].packageCount;
        ++orderCount;
    }

    int nextTime = UNKNOWN;

    for (int t = T; t >= 0; --t) {
        nextOrderTime[t] = nextTime;

        if (orderTimeLine[t].dest != UNKNOWN) {
            nextTime = t;
        }
    }

    vector<int> result = hh.run();

    for (int t = 0; t < T; ++t) {
        cout << result[t] << endl;
    }

    return 0;
}

Measured memory_bytes: 1408