#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("sse4.2")

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <queue>
#include <functional>
#include <numeric>
#include <random>
#include <chrono>
#include <cstring>
#include <climits>
#include <cassert>

#include <x86intrin.h>

using namespace std;

typedef long long int ll;

struct xorshift64 {
  unsigned long long int x = 88172645463325252ULL;
  inline unsigned short nextUShort() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUShortMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x000000000000ffff) * mod) >> 48;
  }
  inline unsigned int nextUInt() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline unsigned int nextUIntMod(unsigned long long int mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return ((x & 0x00000000ffffffff) * mod) >> 32;
  }
  inline unsigned long long int nextULL() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  inline double nextDouble() {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return (double)x * 5.42101086242752217e-20;
  }
};

struct timer {
  double t = 0.0;
  inline void restart() {
    t = now();
  }
  inline double time() {
    return now() - t;
  }
  inline double now() {
    unsigned long long l, h;
    __asm__ ("rdtsc" : "=a"(l), "=d"(h));
    return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9
  }
};

//#define DEBUG

xorshift64 theRandom;
timer theTimer;

constexpr short tLast = 9500;
constexpr short tMax = 10000;
constexpr short vMax = 400;

short tNow = 0;
short pNow = 0;
short lNow = 0;

short V, E;

ll totalScore = 0;

list<pair<short, short> > graphAdj[vMax];
short dist[vMax][vMax];
vector<short> route[vMax][vMax];

vector<vector<short> > order(vMax);
short orderCount[vMax];
short totalOrderCount;
short orderFrequency[vMax];

vector<short> visitOrder, bestVisitOrder;
short visitOrderLength;
short nowEnded, lastEnded;

ll calcScore() {
  short t = tNow;
  ll score = 0;
  short now = pNow;
  short lastSupply = lNow;
  short totalDelivered = 0;
  vector<short> delivered(V);
  short i = 0;
  for (i = 0; i < visitOrderLength; i++) {
    short next = visitOrder[i];
    for (short j = 1; j < route[now][next].size(); j++) {
      t += dist[route[now][next][j-1]][route[now][next][j]]; // move
      if (t > tMax) break; // out of time
      if (route[now][next][j] == 0) lastSupply = t; // resupply if arrived at store
      while (delivered[route[now][next][j]] < orderCount[route[now][next][j]]) {
        if (lastSupply >= order[route[now][next][j]][delivered[route[now][next][j]]]) {
          score += (tMax * tMax) - ((t - order[route[now][next][j]][delivered[route[now][next][j]]]) * (t - order[route[now][next][j]][delivered[route[now][next][j]]]));
          delivered[route[now][next][j]]++; // fill an order
          totalDelivered++;
        }
        else break;
      }
    }
    if (t > tMax) break; // out of time
    now = next;
  }
  nowEnded = i;
  t = min(t, tMax);
  if (t > tNow) score /= (t - tNow); // efficiency
  return score;
}

ll calcScoreAfterLast() {
  short t = tNow;
  ll score = totalScore;
  short now = pNow;
  short lastSupply = lNow;
  short totalDelivered = 0;
  vector<short> delivered(V);
  short i = 0;
  for (i = 0; i < visitOrderLength; i++) {
    short next = visitOrder[i];
    for (short j = 1; j < route[now][next].size(); j++) {
      t += dist[route[now][next][j-1]][route[now][next][j]]; // move
      if (t > tMax) break; // out of time
      if (route[now][next][j] == 0) lastSupply = t; // resupply if arrived at store
      while (delivered[route[now][next][j]] < orderCount[route[now][next][j]]) {
        if (lastSupply >= order[route[now][next][j]][delivered[route[now][next][j]]]) {
          score += (tMax * tMax) - ((t - order[route[now][next][j]][delivered[route[now][next][j]]]) * (t - order[route[now][next][j]][delivered[route[now][next][j]]]));
          delivered[route[now][next][j]]++; // fill an order
          totalDelivered++;
        }
        else break;
      }
    }
    if (t > tMax) break; // out of time
    now = next;
  }
  nowEnded = i;
  return score;
}

vector<short> getAnswer(bool stopAtShop = true) {
  short t = tNow;
  ll score = 0;
  short now = pNow;
  short lastSupply = lNow;
  vector<short> delivered(V);
  vector<short> ans;
  short i = 0;
  for (i = 0; i < visitOrderLength; i++) {
    short next = visitOrder[i];
    if (route[now][next].size() <= 1) continue;
    for (short j = 1; j < route[now][next].size(); j++) {
      short lastT = t;
      t += dist[route[now][next][j-1]][route[now][next][j]]; // move
      for (short k = lastT; k < t; k++) ans.push_back(route[now][next][j] + 1);
      if (t > tMax) break; // out of time
      if (route[now][next][j] == 0) lastSupply = t; // resupply if arrived at store
      while (delivered[route[now][next][j]] < orderCount[route[now][next][j]]) {
        if (lastSupply >= order[route[now][next][j]][delivered[route[now][next][j]]]) {
          score += (tMax * tMax) - ((t - order[route[now][next][j]][delivered[route[now][next][j]]]) * (t - order[route[now][next][j]][delivered[route[now][next][j]]]));
          delivered[route[now][next][j]]++; // fill an order
        }
        else break;
      }
      if (stopAtShop && route[now][next][j] == 0) {
        next = 0;
        break;
      }
    }
    if (t > tMax) break; // out of time
    now = next;
    if (stopAtShop && now == 0) break;
  }
  if (t > tMax && score == 0) ans = vector<short>({-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1});
  totalScore += score;
  return ans;
}

void receiveOrder() {
  int newOrderCount;
  cin >> newOrderCount;
  for (int i = 0; i < newOrderCount; i++) {
    int _id, d;
    cin >> _id >> d;
    order[d-1].push_back(tNow);
    orderCount[d-1]++;
    totalOrderCount++;
  }
  int putItemCount;
  cin >> putItemCount;
  for (int i = 0; i < putItemCount; i++) {
    int _id;
    cin >> _id;
  }
}

void makeAction(int command) {
  // make action
  cout << command << endl;

  // update info
  string verdict;
  cin >> verdict;
  if (verdict == "NG") {
    cerr << "Fatal: NG verdict received on t = " << tNow << ", command = " << command << endl;
    exit(0);
  }
  int deliveredCount;
  cin >> deliveredCount;
  for (int i = 0; i < deliveredCount; i++) {
    int _id;
    cin >> _id;
    if (command > 0) {
      order[command-1].erase(order[command-1].begin());
      orderCount[command-1]--;
      totalOrderCount--;
    }
  }

  tNow++;
  if (command != -1) pNow = command - 1;
  if (pNow == 0) lNow = tNow;
  if (tNow < tMax) receiveOrder();
  else {
    cerr << "All done. Final score = " << totalScore << endl;
    exit(0);
  }
}

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

  theTimer.restart();

  cin >> V >> E;
  for (int i = 0; i < E; i++) {
    int u, v, d;
    cin >> u >> v >> d;
    graphAdj[u-1].emplace_back(d, v-1);
    graphAdj[v-1].emplace_back(d, u-1);
  }
  for (int i = 0; i < V; i++) {
    cin >> orderFrequency[i];
  }
  int _tMax;
  cin >> _tMax;

  // receive first order
  receiveOrder();

  // calculate dist
  for (int i = 0; i < V; i++) {
    priority_queue<pair<int, vector<short> >, vector<pair<int, vector<short> > >, greater<pair<int, vector<short> > > > que;
    vector<bool> visited(V);
    que.emplace(0, vector<short>({i}));
    while (!que.empty()) {
      auto now = que.top();
      que.pop();
      int v = now.second[now.second.size()-1];
      if (visited[v]) continue;
      visited[v] = true;
      dist[i][v] = now.first;
      route[i][v] = now.second;
      for (auto &adj: graphAdj[v]) {
        auto next = now;
        next.first += adj.first;
        next.second.push_back(adj.second);
        que.push(next);
      }
    }
  }


  theRandom.x = ((ll)(random_device()()) << 32) | random_device()();

  visitOrder = vector<short>(15);
  visitOrderLength = visitOrder.size();
  for (int i = 0; i < visitOrderLength; i++) {
    do {
      visitOrder[i] = theRandom.nextUIntMod(V);
    } while (orderCount[visitOrder[i]] == 0 && visitOrder[i] != 0);
  }

  ll score = 1000000;
  ll lastScore = score;
  ll bestScore = score;

  while (tNow < tLast) {

    if (totalOrderCount == 0) { // no order yet
      makeAction(-1);
      continue;
    }
    bestVisitOrder = visitOrder;

    double temperature = bestScore * 0.03;
    double decayRate = 1.8e-5;

    score = calcScore();
    lastScore = score;
    bestScore = score;

    double timeLimit = theTimer.time() + 0.300;

    int iterCount = 0;
    int unUpdated = 0;

    //while (theTimer.time() < timeLimit) {
    while (unUpdated < 100000) {
      double swapRoll = theRandom.nextDouble();
      if (swapRoll < 0.25) { // swap
        int v1 = theRandom.nextUIntMod(visitOrderLength);
        int v2 = theRandom.nextUIntMod(visitOrderLength);
        if (v1 == v2 || visitOrder[v1] == visitOrder[v2]) continue;
        swap(visitOrder[v1], visitOrder[v2]);

        score = calcScore();

        #ifdef DEBUG
        if (iterCount % 10000 == 0) cerr << iterCount << " " << theTimer.time() << " " << score << " " << lastScore << " " << bestScore << " " << lastEnded << " " << temperature << endl;
        #endif

        if (score >= lastScore) {
          lastScore = score;
          if (score > bestScore) {
            bestScore = score;
            bestVisitOrder = visitOrder;
            unUpdated = 0;
          }
        }
        else if (theRandom.nextDouble() < exp((score - bestScore) / temperature)) { // accept
          lastScore = score;
        }
        else { // rollback
          swap(visitOrder[v1], visitOrder[v2]);
        }
      }
      else if (swapRoll < 0.5){ // insert
        int v1 = theRandom.nextUIntMod(visitOrderLength);
        int v2 = theRandom.nextUIntMod(visitOrderLength);
        if (v1 == v2) continue;
        int tmp;
        tmp = visitOrder[v1];
        if (v1 < v2) {
          for (int i = v1; i < v2; i++) visitOrder[i] = visitOrder[i+1];
        }
        else {
          for (int i = v1; i > v2; i--) visitOrder[i] = visitOrder[i-1];
        }
        visitOrder[v2] = tmp;

        score = calcScore();

        #ifdef DEBUG
        if (iterCount % 10000 == 0) cerr << iterCount << " " << theTimer.time() << " " << score << " " << lastScore << " " << bestScore << " " << lastEnded << " " << temperature << endl;
        #endif

        if (score >= lastScore) {
          lastScore = score;
          if (score > bestScore) {
            bestScore = score;
            bestVisitOrder = visitOrder;
            unUpdated = 0;
          }
        }
        else if (theRandom.nextDouble() < exp((score - bestScore) / temperature)) { // accept
          lastScore = score;
        }
        else { // rollback
          tmp = visitOrder[v2];
          if (v2 < v1) {
            for (int i = v2; i < v1; i++) visitOrder[i] = visitOrder[i+1];
          }
          else {
            for (int i = v2; i > v1; i--) visitOrder[i] = visitOrder[i-1];
          }
          visitOrder[v1] = tmp;
        }
      }
      else {
        int v = theRandom.nextUIntMod(visitOrderLength);
        int d = theRandom.nextUIntMod(V);
        if (visitOrder[v] == d) continue;
        //if (visitOrder[v] == d) continue;
        short dBefore = visitOrder[v];
        visitOrder[v] = d;

        score = calcScore();

        #ifdef DEBUG
        if (iterCount % 10000 == 0) cerr << iterCount << " " << theTimer.time() << " " << score << " " << lastScore << " " << bestScore << " " << lastEnded << " " << temperature << endl;
        #endif

        if (score >= lastScore) {
          lastScore = score;
          if (score > bestScore) {
            bestScore = score;
            bestVisitOrder = visitOrder;
            unUpdated = 0;
          }
        }
        else if (theRandom.nextDouble() < exp((score - bestScore) / temperature)) { // accept
          lastScore = score;
        }
        else { // rollback
          visitOrder[v] = dBefore;
        }
      }

      iterCount++;
      unUpdated++;
      temperature *= 1.0 - decayRate;
    }

    visitOrder = bestVisitOrder;
    vector<short> ans = getAnswer();
    for (int i = 0; i < ans.size(); i++) {
      if (i > 0) {
        if (tNow >= tMax && ans[i-1] != ans[i]) break;
      }
      makeAction(ans[i]);
    }
  }

  visitOrder = vector<short>(50);
  visitOrderLength = visitOrder.size();
  for (int i = 0; i < visitOrderLength; i++) {
    do {
      visitOrder[i] = theRandom.nextUIntMod(V);
    } while (orderCount[visitOrder[i]] == 0 && visitOrder[i] != 0);
  }

  while (tNow < tMax) {

    if (totalOrderCount == 0) { // no order yet
      makeAction(-1);
      continue;
    }
    bestVisitOrder = visitOrder;

    double temperature = totalOrderCount * 1000000;
    double decayRate = 5.0e-7;

    score = calcScoreAfterLast();
    lastScore = score;
    bestScore = score;
    lastEnded = nowEnded;

    double timeLimit = 29.800;

    int iterCount = 0;
    int unUpdated = 0;

    while (theTimer.time() < timeLimit) {
      double swapRoll = theRandom.nextDouble();
      if (swapRoll < 0.25) { // swap
        int v1 = theRandom.nextUIntMod(visitOrderLength);
        int v2 = theRandom.nextUIntMod(visitOrderLength);
        if (v1 == v2 || visitOrder[v1] == visitOrder[v2] || min(v1, v2) > lastEnded) continue;
        swap(visitOrder[v1], visitOrder[v2]);

        score = calcScoreAfterLast();

        #ifdef DEBUG
        if (iterCount % 10000 == 0) cerr << iterCount << " " << theTimer.time() << " " << score << " " << lastScore << " " << bestScore << " " << lastEnded << " " << temperature << endl;
        #endif

        if (score >= lastScore) {
          lastScore = score;
          if (score > bestScore) {
            bestScore = score;
            bestVisitOrder = visitOrder;
            unUpdated = 0;
          }
          lastEnded = nowEnded;
        }
        else if (theRandom.nextDouble() < exp((score - bestScore) / temperature)) { // accept
          lastScore = score;
          lastEnded = nowEnded;
        }
        else { // rollback
          swap(visitOrder[v1], visitOrder[v2]);
          if (theRandom.nextDouble() < 0.0001) visitOrder = bestVisitOrder;
        }
      }
      else if (swapRoll < 0.5){ // insert
        int v1 = theRandom.nextUIntMod(visitOrderLength);
        int v2 = theRandom.nextUIntMod(visitOrderLength);
        if (v1 == v2 || min(v1, v2) > lastEnded) continue;
        int tmp;
        tmp = visitOrder[v1];
        if (v1 < v2) {
          for (int i = v1; i < v2; i++) visitOrder[i] = visitOrder[i+1];
        }
        else {
          for (int i = v1; i > v2; i--) visitOrder[i] = visitOrder[i-1];
        }
        visitOrder[v2] = tmp;

        score = calcScoreAfterLast();

        #ifdef DEBUG
        if (iterCount % 10000 == 0) cerr << iterCount << " " << theTimer.time() << " " << score << " " << lastScore << " " << bestScore << " " << lastEnded << " " << temperature << endl;
        #endif

        if (score >= lastScore) {
          lastScore = score;
          if (score > bestScore) {
            bestScore = score;
            bestVisitOrder = visitOrder;
            unUpdated = 0;
          }
          lastEnded = nowEnded;
        }
        else if (theRandom.nextDouble() < exp((score - bestScore) / temperature)) { // accept
          lastScore = score;
          lastEnded = nowEnded;
        }
        else { // rollback
          tmp = visitOrder[v2];
          if (v2 < v1) {
            for (int i = v2; i < v1; i++) visitOrder[i] = visitOrder[i+1];
          }
          else {
            for (int i = v2; i > v1; i--) visitOrder[i] = visitOrder[i-1];
          }
          visitOrder[v1] = tmp;
          if (theRandom.nextDouble() < 0.0001) visitOrder = bestVisitOrder;
        }
      }
      else {
        int v = theRandom.nextUIntMod(visitOrderLength);
        int d = theRandom.nextUIntMod(V);
        if (visitOrder[v] == d || v > lastEnded) continue;
        //if (visitOrder[v] == d) continue;
        short dBefore = visitOrder[v];
        visitOrder[v] = d;

        score = calcScoreAfterLast();

        #ifdef DEBUG
        if (iterCount % 10000 == 0) cerr << iterCount << " " << theTimer.time() << " " << score << " " << lastScore << " " << bestScore << " " << lastEnded << " " << temperature << endl;
        #endif

        if (score >= lastScore) {
          lastScore = score;
          if (score > bestScore) {
            bestScore = score;
            bestVisitOrder = visitOrder;
            unUpdated = 0;
          }
          lastEnded = nowEnded;
        }
        else if (theRandom.nextDouble() < exp((score - bestScore) / temperature)) { // accept
          lastScore = score;
          lastEnded = nowEnded;
        }
        else { // rollback
          visitOrder[v] = dBefore;
          if (theRandom.nextDouble() < 0.0001) visitOrder = bestVisitOrder;
        }
      }

      iterCount++;
      unUpdated++;
      temperature *= 1.0 - decayRate;
    }

    visitOrder = bestVisitOrder;
    vector<short> ans = getAnswer(false);
    for (auto &x: ans) makeAction(x);
  }

  return 0;
}


Measured memory_bytes: 14416