//#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<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 Dijkstra {
  //  int V;
  //  vector<vector<pii>> G;
  //  vector<int> d, pre, cnt;
  //  vector<bool> used;
  //  
  //  Dijkstra(const TestCase& tc) {
  //    V = tc.V;
  //    G.resize(V);
  //    for (const auto& e : tc.edges) {
  //      G[e->u].emplace_back(e->d, e->v);
  //      G[e->v].emplace_back(e->d, e->u);
  //    }

  //    for (int s = 0; s < V; s++) {
  //      build(s);
  //    }
  //  }
  //  
  //  void build(int s) {
  //    d = vector<int>(V, inf);
  //    pre = vector<int>(V, -1);
  //    cnt = vector<int>(V, 0);
  //    used = vector<bool>(V, false);

  //    priority_queue<pii, vector<pii>, greater<pii>> pq;
  //    pq.emplace(0, s);
  //    d[s] = 0;
  //    cnt[s] = 1;
  //    
  //    while (!pq.empty()) {
  //      int mincost, u;
  //      tie(mincost, u) = pq.top(); pq.pop();
  //      if (d[u] < mincost) continue;
  //      for (const auto& e : G[u]) {
  //        int v = e.second;
  //        if (d[u] + e.first < d[v]) {
  //          d[v] = d[u] + e.first;
  //          pq.emplace(d[v], v);
  //          pre[v] = u;
  //          cnt[v] = cnt[u];
  //        }
  //        else if (d[u] + e.first == d[v]) {
  //          cnt[v] += cnt[u];
  //        }
  //      }
  //    }
  //    cerr << s << ": " << cnt << endl;
  //  }
  //};

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

      // order 数で頂点に優先度を設定する
      vector<int> priority(V);
      {
        vector<pii> cnt(V); // (id, cnt)
        for (int i = 0; i < V; i++) cnt[i] = pii(i, 0);
        for (const auto& o : tc.orders) {
          if (o) {
            cnt[o->dst].second++;
          }
        }
        sort(cnt.begin(), cnt.end(), [&](const pii& a, const pii& b) {
          if (a.second == b.second)
            return a.first < b.first;
          return a.second > b.second;
        });
        for (int i = 0; i < V; i++) {
          priority[cnt[i].first] = i;
        }
      }

      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];
            }
            else if (k != i && d[i][k] + d[k][j] == d[i][j]) {
              next[i][j] = priority[j] < priority[k] ? 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 n = 0; n < numLoop; n++) {
        //if (n % 100000 == 0) cerr << score << endl;
        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, n, numLoop);
        double x = -diff / temp;

        if (-diff > temp * lrnd[n & 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);
          }
        }
        //if (n % 1000000 == 0) cerr << accumulate(all(S), 0) << endl;
      }
    }

    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;
            }
          }
        }
        if (n % 1000000 == 0) {
          cerr << s1 << " " << s2 << endl;
        }
      }
    }

    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 TSP6 {
    Xorshift& rnd;

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

    int t0;
    vector<int> p;

    ll oscore;
    int tscore;

    TSP6(const vector<vector<int>>& G, const vector<int>& r, const vector<OrderPtr>& orders, int t0, Xorshift& rnd) : t0(t0), rnd(rnd) {
      map<int, vector<OrderPtr>> orderMap;
      map<int, int> uToI;
      orderMap[0] = vector<OrderPtr>();
      for (const OrderPtr& order : orders) {
        orderMap[order->dst].push_back(order);
      }
      for (auto& e : orderMap) {
        iToU.push_back(e.first);
        uToI[e.first] = iToU.size() - 1;
        iToOs.push_back(e.second);
      }
      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 = r;
      for (int& u : p) u = uToI[u];
      oscore = tscore = 0;
      int t = t0;
      for (int i = 0; i < V; i++) {
        for (const OrderPtr& o : iToOs[i]) {
          oscore += (t - o->t) * (t - o->t);
        }
        t += d[p[i]][p[(i + 1) % V]];
      }
      tscore = t - t0;
    }

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

    pair<ll, int> calcCost() {
      ll oscore = 0;
      int tscore = 0;
      int t = t0;
      for (int i = 0; i < V; i++) {
        for (const OrderPtr& o : iToOs[p[i]])
          oscore += (t - o->t) * (t - o->t);
        t += d[p[i]][p[(i + 1) % V]];
      }
      return pair<ll, int>(oscore, t - t0);
    }

    pair<ll, int> twoOptDiff(int idx1, int idx2) {
      ll po = oscore;
      int pt = tscore;
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
      auto now = calcCost();
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
      return pair<ll, int>(now.first - po, now.second - pt);
    }

    void twoOpt(int idx1, int idx2, const pair<ll, int>& diff) {
      reverse(p.begin() + idx1 + 1, p.begin() + idx2 + 1);
      oscore += diff.first;
      tscore += diff.second;
    }

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

    double eval(ll oscore, int tscore, int loopCnt, int maxLoop) {
      return oscore * 1e-9 + tscore;
    }

    void solve2optSA(int numLoop) {
      double bestScore = DBL_MAX;
      vector<int> bp;
      for (int n = 0; n < numLoop; n++) {
        double prevScore = eval(oscore, tscore, n, numLoop);

        int i1 = rnd.nextUInt() % V;
        int i2 = rnd.nextUInt() % (V - 1);
        if (i2 >= i1) i2++;
        if (i1 > i2) swap(i1, i2);

        auto ret = twoOptDiff(i1, i2);

        double nowScore = eval(oscore + ret.first, tscore + 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]) {
          twoOpt(i1, i2, ret);
          if (nowScore < bestScore) {
            bestScore = nowScore;
            bp = p;
          }
        }
      }
      p = bp;
    }

    pair<int, vector<int>> getDistanceAndRoute() {
      int dist = 0;
      vector<int> route;
      for (int i = 0; i < V; i++) {
        route.push_back(iToU[p[i]]);
        dist += d[p[i]][p[(i + 1) % V]];
      }
      route.push_back(iToU[0]);
      return pair<int, vector<int>>(dist, route);
    }
  };

  struct TSP4 {
    Xorshift& rnd;

    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, Xorshift& rnd) : t0(t0), t1(t1), rnd(rnd) {
      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;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            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;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            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;

          if (-diff > temp * lrnd[n & 0xFFFF]) {
            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 Stats {
    vector<int> routeSize;
    int switchTurn;
    string toString() const {
      ostringstream oss;
      oss << "{" << routeSize[0];
      for (int i = 1; i < (int)routeSize.size(); i++) oss << ", " << routeSize[i];
      oss << "}, " << accumulate(all(routeSize), 0) << ", ";
      oss << switchTurn;
      return oss.str();
    }
  };
  ostream& operator<<(ostream& o, const Stats& s) {
    o << s.toString();
    return o;
  }

  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;

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

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

    Stats stats;

    State() {}

    State(const TestCase& tc, const WarshallFloyd& wf, int seed, int R = 3) : tc(tc), wf(wf), turn(0), R(R) {
      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;
      numOrder = 0;
      for (const auto& o : tc.orders) if (o) numOrder++;
      numDelivered = 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
        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 deliver() {
      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 tick(int w) {
      cmds.push_back(w == -1 ? -1 : w + 1);
      move(w);
      deliver();
      turn++;
      if (turn == TMAX) return;
      order();
      load();
    }

    //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(20000000);

    //  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();
    //    //TSP6 tsp(wf.d, r, orders, turn, rnd);
    //    TSP tsp(wf.d, r, rnd);
    //    tsp.solve2optSA(100000);
    //    tie(d, r) = tsp.getDistanceAndRoute();

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

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

    //    t1 = turn;
    //  }

    //  // 9500 に拠点に帰り、かつ配達数を最大化する移動
    //  // 現在時刻から 9500 までの間の注文地点を訪問する必要性は薄い
    //  vector<OrderPtr> orders;
    //  {
    //    set<int> st;
    //    for (int t = turn; t <= 9500; t++) {
    //      // TODO: 細かい調整
    //      if (tc.orders[t]) {
    //        st.insert(tc.orders[t]->dst);
    //      }
    //    }
    //    for (const auto& o : car.load) {
    //      if (st.find(o->dst) != st.end()) continue;
    //      orders.push_back(o);
    //    }
    //  }
    //  while (car.load.empty() && turn < 9500) tick(-1);
    //  if (!car.load.empty()) {
    //    TSP3 tsp3(wf.d, orders, 9500 - turn, rnd);
    //    tsp3.solve2optSA(12000000);
    //    auto r = tsp3.getDistanceAndRoute();
    //    auto cs = wf.getCommands(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(12000000);
    //    auto r = tsp3.getDistanceAndRoute();
    //    auto cs = wf.getCommands(r.second);
    //    for (int cmd : cs) {
    //      tick(cmd);
    //      if (cmds.size() == TMAX) break;
    //    }
    //  }

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

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

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

    vector<int> getAns2() {
      // 距離和が最小となる 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(20000000);

      stats.routeSize = tsp5.S;

      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();
        //TSP6 tsp(wf.d, r, orders, turn, rnd);
        TSP tsp(wf.d, r, rnd);
        tsp.solve2optSA(100000);
        tie(d, r) = tsp.getDistanceAndRoute();        

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

        // 正方向と負方向でスコアの高いものを採用
        //vector<int> cs = wf.getCommands(r);
        vector<int> cs = chooseBetterDirectionCommands(r);

        // コマンド実行
        for (int cmd : cs) tick(cmd);
        t1 = turn;
      }

      stats.switchTurn = 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(12000000);
        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(12000000);
        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 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();

  init();

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

  ll totalScore = 0;
  int numFinished = 0;

  int totalDelivered = 0;
  int totalOrder = 0;

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

    //{
    //  map<int, int> orderCnt;
    //  for (const auto& o : tc.orders) {
    //    if (o) {
    //      orderCnt[o->dst]++;
    //    }
    //  }
    //  vector<pii> orders;
    //  map<int, int> orderHist;
    //  for (auto& e : orderCnt) {
    //    orders.emplace_back(e.second, e.first);
    //    orderHist[e.second]++;
    //  }
    //  sort(all(orders));
    //  dump(orders);
    //  dump(orderHist);
    //}

    State bestState;
    ll bestScore = 0, bestScore1 = 0, bestScore2 = 0;
    for (int n = 0; n < 3; n++) {
      for (int r = 3; r <= 5; r++) {
        //for (int n = 0; n < 3; n++) {
          //{
          //  State state1(tc, wf, r * (n + 1) * 10007, r);
          //  auto ans = state1.getAns();
          //  NTester::Tester tester(tc, ans);
          //  tester.simulate();
          //  if (bestScore1 < tester.score) {
          //    bestScore1 = tester.score;
          //  }
          //  if (bestScore < tester.score) {
          //    bestState = state1;
          //    bestScore = tester.score;
          //    //cerr << bestScore << endl;
          //  }
          //}
        {
          State state2(tc, wf, r * (n + 1) * 10007, r);
          auto ans = state2.getAns2();
          NTester::Tester tester(tc, ans);
          tester.simulate();
          if (bestScore2 < tester.score) {
            bestScore2 = tester.score;
          }
          if (bestScore < tester.score) {
            bestState = state2;
            bestScore = tester.score;
            //cerr << bestScore << endl;
          }
          //dump(state2.stats, state2.score);
        }
      }
    }

    for (int i : bestState.cmds) out << i << endl;
    in.close();
    out.close();

    totalDelivered += bestState.numDelivered;
    totalOrder += bestState.numOrder;
    totalScore += bestScore;
    numFinished++;

    cerr << i << "/" << numFinished << ": " << double(totalScore) / numFinished * 30.0 << " " << bestState.numDelivered << "/" << bestState.numOrder << " " << bestScore1 << "/" << bestScore2 << endl;
  });

  dump(totalDelivered, totalOrder);
  dump(timer.elapsedMs());

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

  init();

  using namespace NSolver;

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

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

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

  bool timeup = false;
  State bestState;
  ll bestScore = 0;
  for (int n = 0;; n++) {
    for (int r = 3; r <= 5; r++) {
      if (n >= 3 && timer.elapsedMs() > 27000) {
        timeup = true;
        break;
      }
      //for (int n = 0; n < 3; n++) {
      State state(tc, wf, r * (n + 1) * 10007, r);
      auto ans = state.getAns2();
      NTester::Tester tester(tc, ans);
      tester.simulate();
      if (bestScore < tester.score) {
        bestState = state;
        bestScore = tester.score;
        //cerr << bestScore << endl;
      }
    }
    if (timeup) break;
  }

  for (int i : bestState.cmds) out << i << endl;

  dump(bestScore);

  return 0;
}
#endif


Measured memory_bytes: 16488