//#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;
  }
} rnd;

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;

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<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>& p) {
      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 {
    int V;
    vector<int> iToU;
    vector<vector<int>> d;

    int score;
    vector<int> p;

    TSP(const vector<vector<int>>& G, const vector<int>& us) : iToU(us) {
      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;
      const unsigned R = (1 << 30), mask = (1 << 30) - 1;
      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;
        double prob = exp(-diff / temp);

        if (R * prob > (rnd.nextUInt() & mask)) {
          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 TSP2 {
    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) {
      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;
      const unsigned R = (1 << 30), mask = (1 << 30) - 1;
      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;
          double prob = exp(-diff / temp);

          if (R * prob > (rnd.nextUInt() & mask)) {
            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;
          double prob = exp(-diff / temp);

          if (R * prob > (rnd.nextUInt() & mask)) {
            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 {
    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) : tlimit(tlimit) {
      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) {
      const unsigned R = (1 << 30), mask = (1 << 30) - 1;
      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;
          double prob = exp(-diff / temp);

          if (R * prob > (rnd.nextUInt() & mask)) {
            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;
          double prob = exp(-diff / temp);

          if (R * prob > (rnd.nextUInt() & mask)) {
            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;
          double prob = exp(-diff / temp);

          if (R * prob > (rnd.nextUInt() & mask)) {
            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 TSP4 {
    vector<int> iToU;
    vector<vector<OrderPtr>> iToOs;
    //vector<int> iToT;
    vector<vector<int>> d;

    int t0, t1;
    vector<int> p, q;
    double cost;
    
    TSP4(const vector<vector<int>>& G, const vector<OrderPtr>& orders, int t0, int t1) : t0(t0), t1(t1) {
      map<int, vector<OrderPtr>> orderMap;
      orderMap[0] = vector<OrderPtr>();
      for (const OrderPtr& order : orders) {
        orderMap[order->dst].push_back(order);
      }
      for (auto& e : orderMap) {
        iToU.push_back(e.first);
        iToOs.push_back(e.second);
      }
      int V = orderMap.size();
      d.resize(V, vector<int>(V));
      for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
          d[i][j] = d[j][i] = G[iToU[i]][iToU[j]];
        }
      }
      p.resize(V);
      //iToT.resize(V);
      cost = 0;
      int t = t0;
      for (int i = 0; i < V; i++) {
        for (const OrderPtr& o : iToOs[i]) {
          cost += t - o->t;
        }
        //iToT[i] = t;
        t += d[i][(i + 1) % V];
        p[i] = i;
      }
    }

    double calcCost() {
      double cost = 0;
      int t = t0;
      int V = p.size();
      for(int i = 0; i < V; i++) {
        for (const OrderPtr& o : iToOs[p[i]])
          cost += t - o->t;
        t += d[p[i]][p[(i + 1) % V]];
      }
      V = q.size();
      for (int i = 0; i < V; i++) {
        for (const OrderPtr& o : iToOs[q[i]])
          cost += t1 - o->t + dist(0, q[i]);
      }
      return cost;
    }

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

    double twoOptDiff(int idx1, int idx2) {
      double pre = cost;
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
      double now = calcCost();
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
      return now - pre;
    }

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

    double eraseDiff(int idx) {
      double pre = cost;
      int tmp = p[idx];
      q.push_back(tmp);
      p.erase(p.begin() + idx);
      double now = calcCost();
      p.insert(p.begin() + idx, tmp);
      q.pop_back();
      return now - pre;
    }

    void erase(int idx) {
      q.push_back(p[idx]);
      p.erase(p.begin() + idx);
    }

    double insertDiff(int pidx, int qidx) {
      double pre = cost;
      int tmp = q[qidx];
      p.insert(p.begin() + pidx + 1, tmp);
      q.erase(q.begin() + qidx);
      double now = calcCost();
      q.insert(q.begin() + qidx, tmp);
      p.erase(p.begin() + pidx + 1);
      return now - pre;
    }

    void insert(int pidx, int qidx) {
      p.insert(p.begin() + pidx + 1, q[qidx]);
      q.erase(q.begin() + qidx);
    }

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

    void solve2optSA(int numLoop) {
      const unsigned R = (1 << 30), mask = (1 << 30) - 1;
      for (int n = 0; n < numLoop; n++) {
        int r = rnd.nextUInt(3);
        if (r < 1) {
          // 2opt
          if (p.size() <= 2) continue;
          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);

          double diff = twoOptDiff(idx1, idx2);

          double temp = getTemp(100.0, 0.1, n, numLoop);
          double x = -diff / temp;
          double prob = exp(x);

          if (R * prob > (rnd.nextUInt() & mask)) {
            twoOpt(idx1, idx2);
            cost += diff;
          }
        }
        else if (r < 2) {
          // erase
          if (p.size() <= 2) continue;
          
          int idx = rnd.nextUInt(p.size() - 1) + 1;

          double diff = eraseDiff(idx);

          double temp = getTemp(100.0, 0.01, n, numLoop);
          double x = -diff / temp;
          double prob = exp(x);

          if (R * prob > (rnd.nextUInt() & mask)) {
            erase(idx);
            cost += diff;
          }
        }
        else {
          // insert
          if (q.empty()) continue;
          
          int pidx = rnd.nextUInt(p.size());
          int qidx = rnd.nextUInt(q.size());

          double diff = insertDiff(pidx, qidx);

          double temp = getTemp(100.0, 0.01, n, numLoop);
          double x = -diff / temp;
          double prob = exp(x);

          if (R * prob > (rnd.nextUInt() & mask)) {
            insert(pidx, qidx);
            cost += diff;
          }
        }
      }
    }
    
    pair<int, vector<int>> getDistanceAndRoute() {
      vector<int> route;
      int turn = 0, V = p.size();
      for (int i = 0; i < V; i++) {
        route.push_back(iToU[p[i]]);
        turn += dist(p[i], p[(i + 1) % V]);
      }
      route.push_back(iToU[0]);
      return pair<int, vector<int>>(turn, 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 {
    TestCase tc;
    WarshallFloyd wf;

    int turn;
    vector<int> cmds;
    //queue<OrderPtr> que;
    vector<OrderPtr> orderQueue;
    vector<vector<EdgePtr>> dist;
    Car car;
    
    ll score;

    State(const TestCase& tc, const WarshallFloyd& wf) : tc(tc), wf(wf), turn(0) {
      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() {
      OrderPtr o = tc.orders[turn];
      if (!o) return;
      orderQueue.push_back(o);
    }

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

    void move(int w) {
      // 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() {
      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;
      }
    }

    vector<int> gather(int t0, int t1) {
      t1 = min(t1, TMAX);
      // {0} + [t0, t1) にやってくる注文の位置集合
      set<int> st({ 0 });
      map<int, int> mp;
      for (int t = t0; t < t1; t++) {
        const auto& order = tc.orders[t];
        if (order->id == -1) continue;
        st.insert(order->dst);
      }
      //cerr << mp.size() << ": " << mp << endl;
      return vector<int>(st.begin(), st.end());
    }

    vector<OrderPtr> gatherOrders(int t0, int t1) {
      vector<OrderPtr> ret;
      for (int t = t0; t < t1; t++) {
        auto order = tc.orders[t];
        if (order->id == -1) continue;
        ret.push_back(order);
      }
      return ret;
    }

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

    vector<int> getAns3() {
      int t0 = 500, t1 = 1000;
      while (turn < t0) tick(-1);
      while (t1 < 9500) {
        TSP4 tsp4(wf.d, car.load, t0, t1);
        tsp4.solve2optSA(10000000);
        auto r = tsp4.getDistanceAndRoute();
        auto path = wf.getPath(r.second);
        auto cs = wf.getCommands(path);
        for (int cmd : cs) tick(cmd);
        tick(-1);
        t0 = t0 + r.first + 1; t1 = t0 + 500;
      }
      // 9500 に拠点に帰り、かつ配達数を最大化する移動
      TSP3 tsp3(wf.d, car.load, 9500 - turn);
      tsp3.solve2optSA(70000000);
      auto r3 = tsp3.getDistanceAndRoute();
      auto path = wf.getPath(r3.second);
      auto cs = wf.getCommands(path);
      for (int cmd : cs) tick(cmd);
      tick(-1);
      // 残り 500 ターンで配達数最大化
      tsp3 = TSP3(wf.d, car.load, 9999 - turn);
      tsp3.solve2optSA(70000000);
      r3 = tsp3.getDistanceAndRoute();
      path = wf.getPath(r3.second);
      cs = wf.getCommands(path);
      for (int cmd : cs) {
        tick(cmd);
        if (cmds.size() == TMAX) break;
      }
      while (turn < TMAX) tick(-1);
      return cmds;
    }

    vector<int> getAns2() {
      set<int> st1({ 0 }), st2({ 0 });
      for (int u = 1; u < wf.V / 2; u++)
        st1.insert(u);
      for (int u = wf.V / 2; u < wf.V; u++)
        st2.insert(u);
      TSP2 tsp2(wf.d, vector<int>(st1.begin(), st1.end()), vector<int>(st2.begin(), st2.end()));
      tsp2.solve2optSA(100000000);
      st1.clear();
      st2.clear();
      for (int i : tsp2.p1) st1.insert(i);
      for (int i : tsp2.p2) st2.insert(i);

      auto r1 = tsp2.getDistanceAndRoute(1);
      auto r2 = tsp2.getDistanceAndRoute(0);

      int loopcnt = 0;
      int finish = 0, t0 = 0, t1;
      {
        int cnt = 0;
        for (const OrderPtr& o : tc.orders) {
          if (o) {
            cnt++;
            if (cnt == 10) {
              t1 = o->t;
              break;
            }
          }
        }
      }
      while (cmds.size() < TMAX) {
        loopcnt++;
        while (cmds.size() < t1) tick(-1);
        auto s = (loopcnt & 1) ? st1 : st2;
        set<int> st({ 0 });
        for (const auto& o : car.load) 
          if(s.find(o->dst) != s.end())
            st.insert(o->dst);
        auto r = (loopcnt & 1) ? r1 : r2;
        
        // 訪れるべき頂点集合
        for (int i = r.second.size() - 1; i >= 0; i--)
          if (st.find(r.second[i]) == st.end())
            r.second.erase(r.second.begin() + i);

        // ない
        if (r.second.size() == 2) {
          finish = t1 + max(r.first, 10);
          t0 = t1;
          t1 = finish;
          continue;
        }

        int d = 0, K = r.second.size();
        for (int i = 0; i < r.second.size(); i++)
          d += wf.d[r.second[i]][r.second[(i + 1) % K]];

        // TSP
        TSP tsp(wf.d, r.second);
        tsp.solve2optSA(1000000);
        r = tsp.getDistanceAndRoute();

        finish = t1 + max(r.first, 10);
        // 配達終了が 9500 を過ぎる
        if (finish > 9500) break;
        t0 = t1;
        t1 = finish;
        auto path = wf.getPath(r.second);
        auto cs = wf.getCommands(path);
        for (int cmd : cs) tick(cmd);
      }
      // 9500 に拠点に帰り、かつ配達数を最大化する移動
      tick(-1);
      while (car.load.empty() && turn < 9500) tick(-1);
      if (!car.load.empty()) {
        TSP3 tsp3(wf.d, car.load, 9500 - turn);
        tsp3.solve2optSA(120000000);
        auto r3 = tsp3.getDistanceAndRoute();
        auto path = wf.getPath(r3.second);
        auto cs = wf.getCommands(path);
        for (int cmd : cs) tick(cmd);
        tick(-1);
      }
      // 残り 500 ターンで配達数最大化
      while (car.load.empty() && turn < 10000) tick(-1);
      if (!car.load.empty()) {
        TSP3 tsp3 = TSP3(wf.d, car.load, 9999 - turn);
        tsp3.solve2optSA(120000000);
        auto r3 = tsp3.getDistanceAndRoute();
        auto path = wf.getPath(r3.second);
        auto cs = wf.getCommands(path);
        for (int cmd : cs) {
          tick(cmd);
          if (cmds.size() == TMAX) break;
        }
      }

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

}


namespace NTester {

  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 Tester {
    int V, E;

    vector<EdgePtr> edges;
    vector<OrderPtr> orders;

    vector<int> ans;

    int turn;
    queue<OrderPtr> que;
    vector<vector<EdgePtr>> dist;
    Car car;

    ll score;

    Tester() {}
    Tester(const NSolver::TestCase& tc, const vector<int>& ans) {
      V = tc.V;
      E = tc.E;
      edges = tc.edges;
      orders = tc.orders;
      this->ans.resize(TMAX);
      for (int i = 0; i < TMAX; i++) {
        this->ans[i] = ans[i];
        if (this->ans[i] != -1) this->ans[i]--;
      }

      turn = 0;

      dist.resize(V, vector<EdgePtr>(V, nullptr));
      for (auto& e : 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;
    }
    Tester(istream& in, istream& out) {
      in >> V >> E;
      turn = 0;

      for (int t = 0; t < E; t++) {
        int u, v, d;
        in >> u >> v >> d;
        u--; v--;
        edges.emplace_back(new Edge(u, v, d));
      }
      in >> TMAX;
      for (int t = 1; t <= TMAX; t++) {
        int Nnew;
        in >> Nnew;
        if (!Nnew) {
          orders.emplace_back(new Order(-1, t, -1));
        }
        else {
          int newId, dst;
          in >> newId >> dst;
          newId--; dst--;
          orders.emplace_back(new Order(newId, t, dst));
        }
      }

      ans.resize(TMAX);
      for (int i = 0; i < TMAX; i++) {
        out >> ans[i];
        if (ans[i] != -1) ans[i]--;
      }

      dist.resize(V, vector<EdgePtr>(V, nullptr));
      for (auto& e : 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() {
      if (orders[turn]) {
        que.push(orders[turn]);
      }
    }

    void load() {
      if (car.u == 0) {
        while (!que.empty()) {
          car.load.push_back(que.front()); que.pop();
        }
      }
    }

    void move(int w) {
      // 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() {
      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) * (turn - p->t);
        }
        else {
          nload.push_back(p);
        }
        car.load = nload;
      }
    }

    void tick() {
      // 注文発生
      order();
      // 車が店舗にいるなら積み込み
      load();
      // 移動 (ターン経過)
      move(ans[turn++]);
      // 配達
      deliver();
    }

    void simulate() {
      for (int i = 0; i < TMAX; i++)
        tick();
    }
  };
}

//#define DEBUG_MODE
#ifdef DEBUG_MODE
int main() {
  using namespace NSolver;

  timer.measure();

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

  // int i = 4;
  concurrency::parallel_for(1, 101, [&](int i) {
    string input_name = "input/" + to_string(i) + ".txt";
    string output_name = "output/" + to_string(i) + ".txt";
    ifstream in(input_name);
    ofstream out(output_name);

    TestCase tc(in);
    WarshallFloyd wf(tc);
    
    vector<int> bestAns;
    ll bestScore = 0;
    {
      State state(tc, wf);
      auto ans = state.getAns2();
      NTester::Tester tester(tc, ans);
      tester.simulate();
      if (bestScore < tester.score) {
        bestScore = tester.score;
        bestAns = ans;
      }
    }
    for (int i : bestAns) out << i << endl;
    in.close();
    out.close();
    cerr << i << ": " << bestScore << endl;
  });

  return 0;
}
#else
int main() {
  timer.measure();

  using namespace NSolver;

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

  istream& in = cin;
  ostream& out = cout;

  TestCase tc(in);
  WarshallFloyd wf(tc);

  vector<int> bestAns;
  ll bestScore = 0;
  {
    State state(tc, wf);
    auto ans = state.getAns2();
    NTester::Tester tester(tc, ans);
    tester.simulate();
    if (bestScore < tester.score) {
      bestScore = tester.score;
      bestAns = ans;
      dump(state.score, tester.score);
    }
  }
  for (int i : bestAns) out << i << endl;

  return 0;
}
#endif

Measured memory_bytes: 7680