//#define NDEBUG
#include "bits/stdc++.h"
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <array>
#ifdef _MSC_VER
#include <ppl.h>
#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>
#endif

using namespace std;

#define DUMPOUT cerr
#define dump(...) DUMPOUT<<"  ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<"    ";dump_func(__VA_ARGS__)

typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const vector<_Ty>& v) { if (v.empty()) { o << "{ }"; return o; } o << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; }	o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const stack<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } stack<_Ty> t(s); o << "{" << t.top(); t.pop(); while (!t.empty()) { o << ", " << t.top(); t.pop(); } o << "}";	return o; }
template <typename _Ty> ostream& operator << (ostream& o, const list<_Ty>& l) { if (l.empty()) { o << "{ }"; return o; } o << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; }
template <typename _Ty> istream& operator >> (istream& is, vector<_Ty>& v) { for (size_t t = 0; t < v.size(); t++) is >> v[t]; return is; }
namespace aux { // print tuple
  template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
  template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& v) { os << get<N>(v); } };
}

template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys) - 1>::print(os, t); os << "}"; return os; }

template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }

void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }

#define PI 3.14159265358979323846
#define EPS 1e-8
#define FOR(t, a, n) for (int t = (a); t < (n); ++t)
#define REP(t, n) FOR(t, 0, n)
#define all(j) (j).begin(), (j).end()
#define SZ(j) ((int)(j).size())
#define fake false

class Timer {
public:
  double t = 0;
  Timer() {}
  static double time() {
#ifdef _MSC_VER
    return __rdtsc() / 2.8e9;
#else
    unsigned long long a, d;
    __asm__ volatile("rdtsc"
      : "=a"(a), "=d"(d));
    return (d << 32 | a) / 2.8e9;
#endif
  }
  void measure() { t = time() - t; }
  double elapsedMs() { return (time() - t) * 1000.0; }
} timer;

struct Xorshift {
  uint64_t x = 88172645463325252LL;
  unsigned nextUInt() {
    x = x ^ (x << 7);
    return x = x ^ (x >> 9);
  }
  unsigned nextUInt(unsigned mod) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return x % mod;
  }
  unsigned nextUInt(unsigned l, unsigned r) {
    x = x ^ (x << 7);
    x = x ^ (x >> 9);
    return x % (r - l + 1) + l;
  }
  double nextDouble() {
    return double(nextUInt()) / UINT_MAX;
  }
};

template <typename T>
void shuffleVector(vector<T> &v, Xorshift &rnd) {
  int n = v.size();
  for (int t = n - 1; t >= 1; t--) {
    int r = rnd.nextUInt(t);
    swap(v[t], v[r]);
  }
}

int TMAX;
constexpr int inf = INT_MAX / 4;
double lrnd[1 << 16];

void init() {
  Xorshift rnd;
  for (int i = 0; i < 100; i++)
    rnd.nextUInt();
  REP(i, 1 << 16)
    lrnd[i] = log(rnd.nextDouble());
}

struct Edge {
  int u, v, d;
  Edge() {}
  Edge(int u, int v, int d) : u(u), v(v), d(d) {}
};
using EdgePtr = Edge * ;

struct Order {
  int id;
  int t;
  int dst;
  bool completed;
  Order() {}
  Order(int id, int t, int dst) : id(id), t(t), dst(dst), completed(false) {}
};
using OrderPtr = Order * ;

namespace NSolver {

  struct TestCase {
    int V, E;
    vector<EdgePtr> edges;
    vector<int> freqs;
    TestCase() {}
    TestCase(istream &is) {
      is >> V >> E;
      for (int t = 0; t < E; t++) {
        int u, v, d;
        is >> u >> v >> d;
        u--;
        v--;
        edges.emplace_back(new Edge(u, v, d));
      }
      freqs.resize(V);
      for (int u = 0; u < V; u++) {
        is >> freqs[u];
      }
      is >> TMAX;
    }
  };

  //struct TestCase {
  //  int V, E;
  //  vector<EdgePtr> edges;
  //  vector<OrderPtr> orders;

  //  TestCase() {}
  //  TestCase(istream& is) {
  //    is >> V >> E;
  //    for (int t = 0; t < E; t++) {
  //      int u, v, d;
  //      is >> u >> v >> d;
  //      u--; v--;
  //      edges.emplace_back(new Edge(u, v, d));
  //    }
  //    is >> TMAX;
  //    orders.resize(TMAX, nullptr);
  //    for (int t = 0; t < TMAX; t++) {
  //      int Nnew;
  //      is >> Nnew;
  //      if (Nnew) {
  //        int newId, dst;
  //        is >> newId >> dst;
  //        newId--; dst--;
  //        orders[t] = new Order(newId, t, dst);
  //      }
  //    }
  //  }
  //};

  struct WarshallFloyd {
    int V;
    vector<vector<int>> d;
    vector<vector<int>> next;
    WarshallFloyd() {}
    WarshallFloyd(const TestCase &tc) {
      V = tc.V;
      d.resize(V, vector<int>(V, inf));
      next.resize(V, vector<int>(V));
      for (int i = 0; i < V; i++) {
        d[i][i] = 0;
      }
      for (const EdgePtr &e : tc.edges) {
        d[e->u][e->v] = d[e->v][e->u] = e->d;
      }
      for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
          next[i][j] = j;
        }
      }
      for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
          for (int j = 0; j < V; j++) {
            if (d[i][k] + d[k][j] < d[i][j]) {
              d[i][j] = d[i][k] + d[k][j];
              next[i][j] = next[i][k];
            }
          }
        }
      }
    }
    vector<int> getPath(int u, int v) {
      vector<int> ret;
      for (int cur = u; cur != v; cur = next[cur][v]) {
        ret.push_back(cur);
      }
      ret.push_back(v);
      return ret;
    }
    vector<int> getPath(const vector<int> &r) {
      int n = (int)r.size();
      vector<int> path;
      for (int i = 0; i < n - 1; i++) {
        for (int u : getPath(r[i], r[i + 1])) {
          path.push_back(u);
        }
        path.pop_back();
      }
      path.push_back(r[0]);
      return path;
    }
    vector<int> getCommands(const vector<int> &r) {
      vector<int> p = getPath(r);
      vector<int> cmds;
      int n = (int)p.size();
      for (int i = 0; i < n - 1; i++) {
        int u = p[i], v = p[i + 1];
        for (int k = 0; k < d[u][v]; k++) {
          cmds.push_back(v);
        }
      }
      return cmds;
    }
  };

  struct TSP {
    Xorshift &rnd;

    int V;
    vector<int> iToU;
    vector<vector<int>> d;

    int score;
    vector<int> p;

    TSP(const vector<vector<int>> &G, const vector<int> &us, Xorshift &rnd) : iToU(us), rnd(rnd) {
      V = us.size();
      d.resize(V, vector<int>(V));
      for (int i = 0; i < V; i++) {
        for (int j = i; j < V; j++) {
          d[i][j] = d[j][i] = G[us[i]][us[j]];
        }
      }
      score = 0;
      p.resize(V);
      for (int i = 0; i < V; i++) {
        score += d[i][(i + 1) % V];
        p[i] = i;
      }
    }

    inline int dist(int i1, int i2) {
      return d[i1][i2];
    }

    double twoOptDiff(int idx1, int idx2) {
      int p1 = p[idx1], p2 = p[(idx1 + 1) % V], p3 = p[idx2], p4 = p[(idx2 + 1) % V];
      return dist(p1, p3) + dist(p2, p4) - dist(p1, p2) - dist(p3, p4);
    }

    void solve2optClimbing() {
      while (true) {
        bool update = false;
        for (int i1 = 0; i1 < V - 1; i1++) {
          for (int i2 = i1 + 1; i2 < V; i2++) {
            int diff = twoOptDiff(i1, i2);
            if (diff < 0) {
              reverse(p.begin() + i1 + 1, p.begin() + i2 + 1);
              score += diff;
              //cerr << score << endl;
              update = true;
            }
          }
        }
        if (!update)
          break;
      }
    }

    double getTemp(double startTemp, double endTemp, int t, int T) {
      return endTemp + (startTemp - endTemp) * (T - t) / T;
    }

    void solve2optSA(int numLoop) {
      double bestScore = DBL_MAX;
      vector<int> bp;
      for (int i = 0; i < numLoop; i++) {
        int i1 = rnd.nextUInt() % V;
        int i2 = rnd.nextUInt() % (V - 1);
        if (i2 >= i1)
          i2++;
        if (i1 > i2)
          swap(i1, i2);

        double diff = twoOptDiff(i1, i2);

        double temp = getTemp(3.0, 0.01, i, numLoop);
        double x = -diff / temp;

        if (-diff > temp * lrnd[i & 0xFFFF]) {
          reverse(p.begin() + i1 + 1, p.begin() + i2 + 1);
          score += diff;
          if (score < bestScore) {
            bestScore = score;
            bp = p;
          }
        }
      }
      score = bestScore;
      p = bp;
      //cerr << bestScore << endl;
    }

    pair<int, vector<int>> getDistanceAndRoute() {
      vector<int> route;
      for (int i : p)
        route.push_back(iToU[i]);
      route.push_back(iToU[0]);
      return pair<int, vector<int>>(score, route);
    }
  };


  struct TSP5 {
    Xorshift& rnd;
    int R;
    vector<int> V;
    vector<vector<int>> d;
    vector<int> S;
    vector<vector<int>> P;

    inline int dist(int i1, int i2) {
      return d[i1][i2];
    }

    TSP5(const vector<vector<int>>& G, const vector<vector<int>>& us, Xorshift& rnd) : rnd(rnd) {
      d = G;
      P = us;
      R = us.size();
      V.resize(R);
      S.resize(R);
      for (int i = 0; i < R; i++) {
        V[i] = P[i].size();
        for (int j = 0; j < V[i]; j++) {
          S[i] += dist(P[i][j], P[i][(j + 1) % V[i]]);
        }
      }
    }

    int twoOptDiff(int n, int idx1, int idx2) {
      auto& p = P[n];
      int v = p.size();
      int p1 = p[idx1], p2 = p[(idx1 + 1) % v], p3 = p[idx2], p4 = p[(idx2 + 1) % v];
      return dist(p1, p3) + dist(p2, p4) - dist(p1, p2) - dist(p3, p4);
    }

    void twoOpt(int n, int idx1, int idx2) {
      auto& p = P[n];
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
    }

    int swpDiff(int n1, int n2, int idx) {
      auto& p1 = P[n1];
      auto& p2 = P[n2];
      int v1 = V[n1], v2 = V[n2];
      int i1 = p1[idx], i2 = p1[(idx + 1) % v1], i3 = p2[idx], i4 = p2[(idx + 1) % v2];
      return dist(i1, i3) + dist(i2, i4) - dist(i1, i2) - dist(i3, i4);
    }

    void swp(int n1, int n2, int idx) {
      auto& p1 = P[n1];
      auto& p2 = P[n2];
      vector<int> stk1, stk2;
      while (p1.size() > idx) {
        stk1.push_back(p1.back()); p1.pop_back();
      }
      while (p2.size() > idx) {
        stk2.push_back(p2.back()); p2.pop_back();
      }
      while (!stk1.empty()) {
        p2.push_back(stk1.back()); stk1.pop_back();
      }
      while (!stk2.empty()) {
        p1.push_back(stk2.back()); stk2.pop_back();
      }
      V[n1] = p1.size(), V[n2] = p2.size();
      S[n1] = S[n2] = 0;
      for (int i = 0; i < V[n1]; i++) {
        S[n1] += dist(p1[i], p1[(i + 1) % V[n1]]);
      }
      for (int i = 0; i < V[n2]; i++) {
        S[n2] += dist(p2[i], p2[(i + 1) % V[n2]]);
      }
    }

    double getTemp(double startTemp, double endTemp, int t, int T) {
      return endTemp + (startTemp - endTemp) * (T - t) / T;
    }

    void solve2optSA(int numLoop) {
      for (int n = 0; n < numLoop; n++) {
        int r = rnd.nextUInt(1000);
        if (r) {
          int k = rnd.nextUInt(R);
          int v = V[k];
          int i1 = rnd.nextUInt() % v;
          int i2 = rnd.nextUInt() % (v - 1);
          if (i2 >= i1) i2++;
          if (i1 > i2) swap(i1, i2);

          int diff = twoOptDiff(k, i1, i2);

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            twoOpt(k, i1, i2);
            S[k] += diff;
          }
        }
        else {
          int r1 = rnd.nextUInt() % R;
          int r2 = rnd.nextUInt() % (R - 1);
          if (r2 >= r1) r2++;
          if (r1 > r2) swap(r1, r2);
          int v = min(V[r1], V[r2]);
          int idx = rnd.nextUInt(1, v - 1);

          int diff = swpDiff(r1, r2, idx);

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            swp(r1, r2, idx);
          }
        }
      }
    }

    pair<int, vector<int>> getDistanceAndRoute(int k) {
      auto& p = P[k];
      vector<int> route(p);
      route.push_back(0);
      return pair<int, vector<int>>(S[k], route);
    }

  };

  struct TSP2 {
    Xorshift &rnd;

    int V1, V2;
    vector<vector<int>> d;

    int s1, s2;
    vector<int> p1, p2;

    inline int dist(int i1, int i2) {
      return d[i1][i2];
    }

    TSP2(const vector<vector<int>> &G, const vector<int> &us1, const vector<int> &us2, Xorshift &rnd) : rnd(rnd) {
      V1 = (int)us1.size();
      V2 = (int)us2.size();
      d = G;
      p1 = us1;
      p2 = us2;
      s1 = s2 = 0;
      p1.resize(V1);
      p2.resize(V2);
      for (int i = 0; i < V1; i++) {
        s1 += dist(p1[i], p1[(i + 1) % V1]);
      }
      for (int i = 0; i < V2; i++) {
        s2 += dist(p2[i], p2[(i + 1) % V2]);
      }
    }

    int twoOptDiff(const vector<int> &p, int idx1, int idx2) {
      int V = p.size();
      int p1 = p[idx1], p2 = p[(idx1 + 1) % V], p3 = p[idx2], p4 = p[(idx2 + 1) % V];
      return dist(p1, p3) + dist(p2, p4) - dist(p1, p2) - dist(p3, p4);
    }

    void twoOpt(int k, int i1, int i2) {
      vector<int> &p = (k ? p1 : p2);
      reverse(p.begin() + i1 + 1, p.begin() + i2 + 1);
    }

    int swpDiff(int idx) {
      int i1 = p1[idx], i2 = p1[(idx + 1) % V1], i3 = p2[idx], i4 = p2[(idx + 1) % V2];
      return dist(i1, i3) + dist(i2, i4) - dist(i1, i2) - dist(i3, i4);
    }

    void swp(int idx) {
      vector<int> stk1, stk2;
      while (p1.size() > idx) {
        stk1.push_back(p1.back());
        p1.pop_back();
      }
      while (p2.size() > idx) {
        stk2.push_back(p2.back());
        p2.pop_back();
      }
      while (!stk1.empty()) {
        p2.push_back(stk1.back());
        stk1.pop_back();
      }
      while (!stk2.empty()) {
        p1.push_back(stk2.back());
        stk2.pop_back();
      }
      V1 = p1.size();
      V2 = p2.size();
      s1 = s2 = 0;
      for (int i = 0; i < V1; i++) {
        s1 += dist(p1[i], p1[(i + 1) % V1]);
      }
      for (int i = 0; i < V2; i++) {
        s2 += dist(p2[i], p2[(i + 1) % V2]);
      }
    }

    double getTemp(double startTemp, double endTemp, int t, int T) {
      return endTemp + (startTemp - endTemp) * (T - t) / T;
    }

    void solve2optSA(int numLoop) {
      int bestScore = INT_MAX;
      for (int n = 0; n < numLoop; n++) {
        int r = rnd.nextUInt(1000);
        if (r) {
          int k = rnd.nextUInt(2);
          int V = k ? V1 : V2;
          int i1 = rnd.nextUInt() % V;
          int i2 = rnd.nextUInt() % (V - 1);
          if (i2 >= i1)
            i2++;
          if (i1 > i2)
            swap(i1, i2);

          vector<int> &p = k ? p1 : p2;
          int diff = twoOptDiff(p, i1, i2);

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            twoOpt(k, i1, i2);
            (k ? s1 : s2) += diff;
            if (s1 + s2 < bestScore) {
              bestScore = s1 + s2;
            }
          }
        }
        else {
          int V = min(V1, V2);
          int v = rnd.nextUInt(1, V - 1);

          int diff = swpDiff(v);

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            swp(v);
            if (s1 + s2 < bestScore) {
              bestScore = s1 + s2;
            }
          }
        }
      }
    }

    pair<int, vector<int>> getDistanceAndRoute(int k) {
      vector<int> &p = k ? p1 : p2;
      vector<int> route(p);
      route.push_back(0);
      return pair<int, vector<int>>(k ? s1 : s2, route);
    }
  };

  struct TSP3 {
    Xorshift &rnd;

    vector<int> iToU;
    vector<int> iToOC;
    vector<vector<int>> d;

    int tcount;
    int ocount;
    vector<int> p, q;

    int tlimit;

    TSP3(const vector<vector<int>> &G, const vector<OrderPtr> &orders, int tlimit, Xorshift &rnd) : tlimit(tlimit), rnd(rnd) {
      map<int, int> orderCnt;
      orderCnt[0] = 0;
      for (const OrderPtr &order : orders) {
        orderCnt[order->dst]++;
      }
      for (auto &e : orderCnt) {
        iToU.push_back(e.first);
        iToOC.push_back(e.second);
      }
      int V = orderCnt.size();
      d.resize(V, vector<int>(V));
      for (int i = 0; i < V; i++) {
        for (int j = i; j < V; j++) {
          d[i][j] = d[j][i] = G[iToU[i]][iToU[j]];
        }
      }
      p.resize(V);
      tcount = ocount = 0;
      for (int i = 0; i < V; i++) {
        tcount += d[i][(i + 1) % V];
        ocount += iToOC[i];
        p[i] = i;
      }
    }

    inline int dist(int i1, int i2) {
      return d[i1][i2];
    }

    int twoOptDiff(int idx1, int idx2) {
      int V = p.size();
      int p1 = p[idx1], p2 = p[(idx1 + 1) % V], p3 = p[idx2], p4 = p[(idx2 + 1) % V];
      return dist(p1, p3) + dist(p2, p4) - dist(p1, p2) - dist(p3, p4);
    }

    void twoOpt(int idx1, int idx2) {
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
    }

    pii eraseDiff(int idx) {
      int V = p.size();
      int p1 = p[idx], p0 = p[(idx - 1 + V) % V], p2 = p[(idx + 1) % V];
      int tdiff = dist(p0, p2) - dist(p0, p1) - dist(p1, p2);
      int odiff = -iToOC[p1];
      return { tdiff, odiff };
    }

    void erase(int idx, const pii &diff) {
      q.push_back(p[idx]);
      p.erase(p.begin() + idx);
      tcount += diff.first;
      ocount += diff.second;
    }

    pii insertDiff(int pidx, int qidx) {
      int V = p.size();
      int p0 = p[pidx], p1 = q[qidx], p2 = p[(pidx + 1) % V];
      int tdiff = dist(p0, p1) + dist(p1, p2) - dist(p0, p2);
      int odiff = iToOC[p1];
      return { tdiff, odiff };
    }

    void insert(int pidx, int qidx, const pii &diff) {
      p.insert(p.begin() + pidx + 1, q[qidx]);
      q.erase(q.begin() + qidx);
      tcount += diff.first;
      ocount += diff.second;
    }

    double getTemp(double startTemp, double endTemp, int t, int T) {
      return endTemp + (startTemp - endTemp) * (T - t) / T;
    }

    double eval(int tscore, int oscore, int loopCnt, int maxLoop) {
      return -oscore + max(0, tscore - tlimit) * double(loopCnt) / maxLoop;
    }

    void solve2optSA(int numLoop) {
      for (int n = 0; n < numLoop; n++) {
        int r = rnd.nextUInt(10);

        int prevScore = eval(tcount, ocount, n, numLoop);
        if (r < 1) {
          // erase
          if (p.size() <= 2)
            continue;

          int idx = rnd.nextUInt(p.size() - 1) + 1;

          auto ret = eraseDiff(idx);
          double nowScore = eval(tcount + ret.first, ocount + ret.second, n + 1, numLoop);
          double diff = nowScore - prevScore;

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            erase(idx, ret);
          }
        }
        else if (r < 2) {
          // insert
          if (q.empty())
            continue;

          int pidx = rnd.nextUInt(p.size());
          int qidx = rnd.nextUInt(q.size());

          auto ret = insertDiff(pidx, qidx);
          double nowScore = eval(tcount + ret.first, ocount + ret.second, n + 1, numLoop);
          double diff = nowScore - prevScore;

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            insert(pidx, qidx, ret);
          }
        }
        else {
          // 2opt
          int V = p.size();
          int idx1 = rnd.nextUInt() % V;
          int idx2 = rnd.nextUInt() % (V - 1);
          if (idx2 >= idx1)
            idx2++;
          if (idx1 > idx2)
            swap(idx1, idx2);

          int diff = twoOptDiff(idx1, idx2);

          double temp = getTemp(3.0, 0.01, n, numLoop);
          double x = -diff / temp;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
            tcount += diff;
          }
        }
      }
    }

    pair<int, vector<int>> getDistanceAndRoute() {
      vector<int> route;
      for (int i : p)
        route.push_back(iToU[i]);
      route.push_back(iToU[0]);
      return pair<int, vector<int>>(tcount, route);
    }
  };

  struct Car {
    int u;                 // 現在頂点　-1 なら辺上
    EdgePtr e;             // 現在辺
    int x;                 // e.u からの距離
    vector<OrderPtr> load; // 積荷
    Car() {}
    Car(int u) : u(u), e(nullptr), x(-1) {}
  };

  struct State {
    Xorshift rnd;

    TestCase tc;
    WarshallFloyd wf;
    istream &in;
    ostream &out;

    int turn;
    vector<int> cmds;
    vector<OrderPtr> orderQueue;
    vector<vector<EdgePtr>> dist;
    Car car;

    ll score;
    int numOrder;
    int numDelivered;
    int R;

    State(const TestCase &tc, const WarshallFloyd &wf, istream &in, ostream &out, int seed, int R = 3) : tc(tc), wf(wf), in(in), out(out), turn(0), R(3) {
      rnd.x = seed;
      for (int i = 0; i < 1000; i++)
        rnd.nextUInt();
      dist.resize(tc.V, vector<EdgePtr>(tc.V, nullptr));
      for (auto &e : tc.edges) {
        dist[e->u][e->v] = new Edge(e->u, e->v, e->d);
        dist[e->v][e->u] = new Edge(e->v, e->u, e->d);
      }
      car = Car(0);
      score = 0;
    }

    void order() {
      int Nnew;
      in >> Nnew;
      for (int i = 0; i < Nnew; i++) {
        int id, dst;
        in >> id >> dst;
        id--;
        dst--;
        OrderPtr o = new Order(id, turn, dst);
        orderQueue.push_back(o);
      }
      int Nput;
      in >> Nput;
      for (int i = 0; i < Nput; i++) {
        int buf;
        in >> buf;
      }
    }

    void load() {
      if (car.u == 0) {
        for (const auto &o : orderQueue)
          car.load.push_back(o);
        orderQueue.clear();
      }
    }

    void move(int w) {
      out << (w == -1 ? -1 : w + 1) << endl;

      // stay
      if (w == -1)
        return;
      // move
      if (car.u != -1) {
        // 車が頂点 u にいるなら、 {u, w} in edges
        assert(dist[car.u][w]);
        car.e = dist[car.u][w];
        car.x = 1;
        car.u = -1;
      }
      else {
        // edge{u, v} 上にいるなら、u = w or v = w
        assert(car.e && (car.e->u == w || car.e->v == w));
        if (w == car.e->u) {
          // u 方向
          car.x--;
        }
        else {
          // v 方向
          car.x++;
        }
      }
      // 到着判定
      if (car.e && (car.x == 0 || car.x == car.e->d)) {
        if (car.x == 0) {
          // u に到着
          car.u = car.e->u;
          car.e = nullptr;
          car.x = -1;
        }
        else {
          // v に到着
          car.u = car.e->v;
          car.e = nullptr;
          car.x = -1;
        }
      }
    }

    void deliver() {
      string verdict;
      in >> verdict;
      if (verdict == "NG") {
        exit(1);
      }
      int Nachieve;
      in >> Nachieve;
      for (int i = 0; i < Nachieve; i++) {
        int buf;
        in >> buf;
      }

      if (car.e)
        return;
      int u = car.u;
      // u で配達できるものを配達
      vector<OrderPtr> nload;
      for (auto p : car.load) {
        if (u == p->dst) {
          score += TMAX * TMAX - (turn - p->t + 1) * (turn - p->t + 1);
          p->completed = true;
        }
        else {
          nload.push_back(p);
        }
        car.load = nload;
      }
    }

    //void orderLocal() {
    //  OrderPtr o = tc.orders[turn];
    //  if (!o) return;
    //  orderQueue.push_back(o);
    //}

    void loadLocal() {
      if (car.u == 0) {
        for (const auto& o : orderQueue)
          car.load.push_back(o);
        orderQueue.clear();
      }
    }

    void moveLocal(int w) {
      // stay
      if (w == -1) return;
      // move
      if (car.u != -1) {
        // 車が頂点 u にいるなら、 {u, w} in edges
        if (!dist[car.u][w]) {
          dump(car.u, w, wf.V);
        }
        assert(dist[car.u][w]);
        car.e = dist[car.u][w];
        car.x = 1;
        car.u = -1;
      }
      else {
        // edge{u, v} 上にいるなら、u = w or v = w
        assert(car.e && (car.e->u == w || car.e->v == w));
        if (w == car.e->u) {
          // u 方向
          car.x--;
        }
        else {
          // v 方向
          car.x++;
        }
      }
      // 到着判定
      if (car.e && (car.x == 0 || car.x == car.e->d)) {
        if (car.x == 0) {
          // u に到着
          car.u = car.e->u;
          car.e = nullptr;
          car.x = -1;
        }
        else {
          // v に到着
          car.u = car.e->v;
          car.e = nullptr;
          car.x = -1;
        }
      }
    }

    void deliverLocal() {
      if (car.e) return;
      int u = car.u;
      // u で配達できるものを配達
      vector<OrderPtr> nload;
      for (auto o : car.load) {
        if (u == o->dst) {
          score += TMAX * TMAX - (turn - o->t + 1) * (turn - o->t + 1);
          o->completed = true;
          numDelivered++;
        }
        else {
          nload.push_back(o);
        }
        car.load = nload;
      }
    }

    void tickLocal(int w) {
      cmds.push_back(w == -1 ? -1 : w + 1);
      moveLocal(w);
      deliverLocal();
      turn++;
      if (turn == TMAX) return;
      //orderLocal();
      loadLocal();
    }

    void tick(int w) {
      cmds.push_back(w == -1 ? -1 : w + 1);
      move(w);
      deliver();
      turn++;
      if (turn == TMAX)
        return;
      order();
      load();
    }

    vector<int> chooseBetterDirectionCommands(vector<int> fwd) {
      auto fcmds = wf.getCommands(fwd);
      State fstate(*this);
      for (int cmd : fcmds) fstate.tickLocal(cmd);

      vector<int> bck(fwd);
      reverse(bck.begin(), bck.end());
      auto bcmds = wf.getCommands(bck);
      State bstate(*this);
      for (int cmd : bcmds) bstate.tickLocal(cmd);
      //dump(turn, fstate.score - bstate.score);
      return fstate.score < bstate.score ? bcmds : fcmds;
    }

    vector<int> getAns() {
      // 距離和が最小となる 3 つの巡回路を求める
      vector<vector<int>> us(R);
      for (int r = 0; r < R; r++) {
        us[r].push_back(0);
        for (int i = max(1, wf.V * r / R); i < wf.V * (r + 1) / R; i++) {
          us[r].push_back(i);
        }
      }
      TSP5 tsp5(wf.d, us, rnd);
      tsp5.solve2optSA(250000000);
      vector<set<int>> sts(R);
      for (int i = 0; i < R; i++) {
        for (int j : tsp5.P[i]) sts[i].insert(j);
      }
      vector<int> ds(R);
      vector<vector<int>> rs(R);
      for (int i = 0; i < R; i++)
        tie(ds[i], rs[i]) = tsp5.getDistanceAndRoute(i);

      // 時刻 0 での荷物積み込み
      order();
      load();

      // 発注が来るまで待機
      while (car.load.empty()) tick(-1);
      int t1 = turn;

      // 2 つの巡回路を交互に巡回
      // 荷物のある頂点のみ選択して都度 tsp
      int loopcnt = 0;
      while (true) {
        // 巡回路の頂点集合
        auto& st = sts[loopcnt % R];

        // 訪れるべき部分集合
        set<int> subst({ 0 });
        // 車両に積載されている荷物の配送先を調べる
        for (const auto& o : car.load)
          if (st.find(o->dst) != st.end())
            subst.insert(o->dst);

        // 巡回順にする
        vector<int> r = rs[loopcnt % R];
        for (int i = r.size() - 1; i >= 0; i--)
          if (subst.find(r[i]) == subst.end())
            r.erase(r.begin() + i);

        r.pop_back();

        loopcnt++;
        // 巡回すべき頂点がない場合 ( {0} )
        if (r.size() == 1) {
          // 全部配達し終えた場合
          if (numOrder == numDelivered) break;
          // 荷物が来るまで待機
          while (car.load.empty()) tick(-1);
          continue;
        }

        // 部分集合に対して tsp
        int d = 0, K = r.size();
        TSP tsp(wf.d, r, rnd);
        tsp.solve2optSA(1500000);
        tie(d, r) = tsp.getDistanceAndRoute();

        // 配達終了が 9500 を過ぎる
        if (t1 + d > 9500) break;

        // コマンド実行
        //auto cs = wf.getCommands(r);
        auto cs = chooseBetterDirectionCommands(r);
        for (int cmd : cs) tick(cmd);

        t1 = turn;
      }

      // 9500 に拠点に帰り、かつ配達数を最大化する移動
      while (car.load.empty() && turn < 9500) tick(-1);
      if (!car.load.empty()) {
        TSP3 tsp3(wf.d, car.load, 9500 - turn, rnd);
        tsp3.solve2optSA(150000000);
        auto r = tsp3.getDistanceAndRoute();
        //auto cs = wf.getCommands(r.second);
        auto cs = chooseBetterDirectionCommands(r.second);
        for (int cmd : cs) tick(cmd);
      }

      // 残りターンで配達数最大化
      while (car.load.empty() && turn < 10000) tick(-1);
      if (!car.load.empty() && turn < 10000) {
        TSP3 tsp3 = TSP3(wf.d, car.load, 9999 - turn, rnd);
        tsp3.solve2optSA(150000000);
        auto r = tsp3.getDistanceAndRoute();
        //auto cs = wf.getCommands(r.second);
        auto cs = chooseBetterDirectionCommands(r.second);
        for (int cmd : cs) {
          tick(cmd);
          if (cmds.size() == TMAX) break;
        }
      }

      while (cmds.size() < TMAX) tick(-1);
      return cmds;
    }
  };

} // namespace NSolver

int main() {
  timer.measure();

  using namespace NSolver;

  cin.tie(0);
  ios::sync_with_stdio(false);

  init();

  TestCase tc(cin);
  WarshallFloyd wf(tc);

  State state(tc, wf, cin, cout, 1000000007, 4);
  state.getAns();

  return 0;
}


Measured memory_bytes: 11816