#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 = 0.4;
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];
ll penalty[MAX_T + 10];
queue<int> g_path;
int nextActions[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;
    bool delivered;
    int time;

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

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];
int deliveredCount[MAX_T + 10];
int frequency[MAX_V];

class HokudaiHitachi {
public:
    void init() {
        memset(nextActions, WAIT_COMMAND, sizeof(nextActions));

        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);
        }
    }

    void run(int current, int time, int updated_at) {
        int before = 0;
        int dc = 0;
        vector<int> path;
        memset(deliveredCount, 0, sizeof(deliveredCount));

        fprintf(stderr, "Run: current %d, time %d, updated_at %d\n", current, time, updated_at);
        vector<int> packList = getPackageList(0, time);

        // No action
        if (packList.empty()) {
            return;
        }

        vector<int> stockOrder = getPackageList(updated_at + 1, time);
        int stockSize = stockOrder.size();
        double rate = stockSize / (max(1, cost[current][STORE_ID]));

        if (current != STORE_ID && stockSize > 0 && rate >= 4.0) {
            fprintf(stderr, "%d: Return to basement\n", time);
            PathInfo pathinfo = getPath(current, STORE_ID);

            vector<int> path = path2answer(pathinfo.path, current);

            fprintf(stderr, "Return path %d => ", current);
            for (int i = 0; i < path.size(); ++i) {
                int t = time + i;
                if (t > T) break;
                fprintf(stderr, "%d => ", path[i]);
                nextActions[t] = path[i];
            }
            for (int t = time + path.size(); t <= T; ++t) {
                nextActions[t] = WAIT_COMMAND;
            }
            fprintf(stderr, "\n");

            return;
        } else if (current != STORE_ID) {
            return;
        }

        assert(current == STORE_ID);
        if (time != updated_at) {
            fprintf(stderr, "time %d, updated_at %d\n", time, updated_at);
        }
        assert(time - 1 == updated_at);
        vector<int> result = buildDeliveryPath(packList, time);

        bool flg = true;
        int started_at = time;
        int pathCost = 0;
        assert(vertexList.size() == V);

        for (int i = 0; i < result.size() && flg; ++i) {
            int to = result[i];

            fprintf(stderr, "Search simple path: %d -> %d\n", current, to);
            PathInfo pathinfo = getPath(current, to);
            pathCost += pathinfo.dist;

            fprintf(stderr, "Path Dist = %d, StockSize = %d\n", pathinfo.dist, stockSize);

            for (int j = 0; j < pathinfo.path.size(); ++j) {
                int dst = pathinfo.path[j];

                // time += cost[current][dst];

                path.push_back(dst);
                current = dst;

                if (current == STORE_ID) {
                    flg = false;
                    break;
                }
            }
        }

        if (current != STORE_ID) {
            pathCost += cost[current][STORE_ID];
            // time += cost[current][STORE_ID];
            path.push_back(STORE_ID);
        }

        vector<int> npath = path2answer(path);
        assert(vertexList.size() == V);

        for (int i = 0; i < npath.size(); ++i) {
            int t = time + i;

            if (t > T) {
                nextActions[T] = WAIT_COMMAND;
            } else {
                nextActions[t] = npath[i];
            }
            assert(vertexList.size() == V);
        }
    }

    vector<int> getPackageList(int from, int to) {
        vector<int> result;
        bool checked[V];
        memset(checked, false, sizeof(checked));

        to = min(to, T);

        // if (to >= T) return result;
        int cnt = 0;

        for (int t = from; t <= to; ++t) {
            int dest = orderTimeLine[t].dest;

            if (dest == UNKNOWN) continue;
            if (orderTimeLine[t].delivered) continue;
            ++cnt;
            if (checked[dest]) continue;
            checked[dest] = true;

            result.push_back(dest);
        }

        // fprintf(stderr, "%d: Package Count = %d\n", to, cnt);
        fprintf(stderr, "getPackageList to %d, size = %d\n", to, (int) result.size());

        return result;
    }

    vector<int> greedyPath(vector<int> &packageList) {
        vector<int> result;

        map<int, bool> checked;
        int len = packageList.size();
        int current = STORE_ID;

        for (int i = 0; i < len; ++i) {
            int minDist = INF;
            int bestId = -1;

            for (int j = 0; j < len; ++j) {
                int dest = packageList[j];
                int dist = cost[current][dest];

                if (checked[dest]) continue;

                if (minDist > dist) {
                    minDist = dist;
                    bestId = dest;
                }
            }

            assert(bestId != -1);
            result.push_back(bestId);
            current = bestId;
            checked[bestId] = true;
        }

        return result;
    }

    vector<int> buildDeliveryPath(vector<int> &packageList, int started_at) {
        if (packageList.size() <= 2) return packageList;

        packageList = greedyPath(packageList);

        vector<int> bestPath = packageList;
        vector<int> path = bestPath;
        vector<int> currentPath = bestPath;
        ll bestScore = calcScore(bestPath, started_at);
        ll currentScore = bestScore;
        startCycle = getCycle();

        fprintf(stderr, "%5d: buildDeliveryPath (%d) - FirstScore = %lld\n", started_at, (int) packageList.size(),
                bestScore);

        double currentTime = getTime(startCycle);
        int tryCount = 0;
        int len = path.size();

        int R = 500000;
        double k = 2.5;
        double diffScore;
        double avediff = 0.0;
        double totalDiff = 0.0;
        int dcnt = 0;

        while (currentTime < TIME_LIMIT) {
            currentTime = getTime(startCycle);
            double remainTime = (TIME_LIMIT - currentTime) / TIME_LIMIT;

            int type = xor128() % 3;

            int i, j, a, b, temp;

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

            switch (type) {
                case 0:
                    swap(path[i], path[j]);
                    break;
                case 1:
                    temp = path[i];
                    path.erase(path.begin() + i);
                    path.insert(path.begin() + j, temp);
                    break;
                case 2:
                    if (i > j) {
                        temp = i;
                        i = j;
                        j = temp;
                    }

                    a = i;
                    b = j;

                    while (i < j) {
                        swap(path[i], path[j]);

                        ++i;
                        --j;
                    }
                    break;
            }

            ll score = calcScore(path, started_at);
            diffScore = (score - currentScore) / 500.0;

            if (diffScore < 0) {
                ++dcnt;
                totalDiff += diffScore;
                avediff = totalDiff / dcnt;
            }

            if (currentScore < score || (-diffScore < 2.0 * avediff && xor128() % R < R * exp(diffScore / (k * sqrt(remainTime))))) {
                currentPath = path;
                currentScore = score;

                if (bestScore < score) {
                    bestScore = score;
                    bestPath = path;
                }
            } else {
                switch (type) {
                    case 0:
                        swap(path[i], path[j]);
                        break;
                    case 1:
                        path = currentPath;
                        break;
                    case 2:
                        path = currentPath;
                        break;
                }
            }

            ++tryCount;
        }

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

        return bestPath;
    }

    vector<int> path2answer(vector<int> &path, int current = STORE_ID) {
        int time = 0;
        vector<int> answer;

        for (int i = 0; i < path.size() && time < MAX_T; ++i) {
            int dest = path[i];
            if (dest == WAIT_COMMAND) {
                answer.push_back(WAIT_COMMAND);
                continue;
            }

            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;
            }
        }

        return answer;
    }

    ll calcScore(vector<int> &path, int started_at) {
        assert(vertexList.size() == V);
        ll totalScore = 0;
        int time = started_at;
        int current = STORE_ID;

        for (int i = 0; i < path.size() && time < T; ++i) {
            int dest = path[i];

            if (current == STORE_ID) {
                started_at = time;
            }

            if (dest == WAIT_COMMAND) {
                ++time;
                continue;
            }

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

                time += cost[current][dest];
                current = dest;
            }

            if (time > MAX_T) {
                break;
            }

            // delivered order
            int cnt = deliveredCount[current];
            Vertex *vertex = &vertexList[current];

            // fprintf(stderr, "cnt %d, packageCount %d, started_at %d\n", cnt, vertex->packageCount, started_at);

            while (cnt < vertex->packageCount && vertex->deliver_times[cnt] <= started_at) {
                int delay = time - vertex->deliver_times[cnt];
                totalScore += BASE_SCORE - penalty[delay];
                ++cnt;
            }
        }

        time += cost[current][STORE_ID];

        return totalScore;
    }

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

        fprintf(stderr, "Search Path %d -> %d\n", from, to);

        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);
            }
        }

        fprintf(stderr, "Start %d => ", from);
        for (int i = 0; i < pathInfo.path.size(); ++i) {
            fprintf(stderr, "%d => ", pathInfo.path[i]);
        }
        fprintf(stderr, "\n");

        return pathInfo;
    }

};

bool readTurnInfo(int t) {
    int N_new, N_put;
    int id, dst;
    bool updated = false;
    orderCount = 0;

    cin >> N_new;
    if (N_new != 0) {
        cin >> id >> dst;
        --dst;
        Order order(id, dst, false, t);
        orderTimeLine[t] = order;

        fprintf(stderr, "%d: Set order (%d, %d)\n", t, id, dst);

        orderList.push_back(order);
        vertexList[dst].deliver_times.push_back(t);
        ++vertexList[dst].packageCount;
        ++orderCount;
        updated = true;
    }

    cin >> N_put;
    int putId;
    for (int i = 0; i < N_put; ++i) {
        cin >> putId;
        --putId;
        // Order *order = &orderList[putId];

        // ++deliveredCount[order->dest];
        // orderTimeLine[order->time].delivered = true;
    }

    return updated;
}

bool checkMyAction() {
    string verdict;
    cin >> verdict;

    cerr << verdict << endl;

    if (verdict == "NG") {
        return false;
    }

    int N;
    cin >> N;

    int achieveId;

    for (int i = 0; i < N; ++i) {
        cin >> achieveId;
    }

    return true;
}

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

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

        vertexList.push_back(vertex);
    }

    assert(vertexList.size() == V);

    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);

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

    cin >> T;
    int current = STORE_ID;
    int updated_at = 0;
    int next = -1;
    int stepCount = 0;
    bool onVertex;
    bool updated[MAX_T];
    memset(updated, false, sizeof(updated));

    for (int t = 0; t < T; ++t) {
        // assert(t < 1500);
        assert(vertexList.size() == V);
        if (t == 0) {
            onVertex = true;
        } else if (next != WAIT_COMMAND && stepCount == cost[current][next]) {
            current = nextActions[t - 1] - 1;
            onVertex = true;
            if (current == STORE_ID) updated_at = t - 1;
        } else {
            onVertex = (nextActions[t - 1] == WAIT_COMMAND);
        }

        if (onVertex) {
            Vertex *vertex = &vertexList[current];
            int cnt = deliveredCount[current];

            while (cnt < vertex->packageCount && vertex->deliver_times[cnt] <= updated_at) {
                fprintf(stderr, "%d: Delivery success (%d, %d <= %d)\n", t, current,
                        vertex->deliver_times[cnt],
                        updated_at);
                orderTimeLine[vertex->deliver_times[cnt]].delivered = true;
                ++cnt;
            }

            deliveredCount[current] = cnt;
        }

        if (current != WAIT_COMMAND && next != WAIT_COMMAND) {
            assert(cost[current][next] != INF);
        }

        updated[t] = readTurnInfo(t);

        if (next == WAIT_COMMAND) {
            assert(current == STORE_ID);
        }

        if (t > 0 && onVertex) {
            hh.run(current, t, updated_at);
        } else {
            fprintf(stderr, "%d: NO ACTION\n", t);
        }
        cout << nextActions[t] << endl;

        assert(nextActions[t] != 0);

        if (nextActions[t] == WAIT_COMMAND) {
            next = WAIT_COMMAND;
            stepCount = 0;
        } else {
            int nextTarget = nextActions[t] - 1;
            if (nextTarget != next) {
                next = nextTarget;
                stepCount = 1;
            } else {
                ++stepCount;
            }
        }

        if (current != WAIT_COMMAND && next != WAIT_COMMAND) {
            fprintf(stderr, "Turn %d: current %d, next %d, stepCount (%d/%d), onVertex = %d, action = %d\n", t, current,
                    next, stepCount, cost[current][next], onVertex, nextActions[t]);
        } else {
            fprintf(stderr, "Turn %d: current %d, next %d, stepCount %d, onVertex = %d, action = %d\n", t, current,
                    next, stepCount, onVertex, nextActions[t]);
        }

        bool success = checkMyAction();

        if (!success) break;

        if (onVertex && current == STORE_ID) {
            updated_at = t;
        }
    }

    return 0;
}

Measured memory_bytes: 2384