//#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); }
};
} // namespace aux

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

    vector<int> priority = tc.freqs;

    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 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++)
    {
      int v = P[i].size();
      //V[i] = P[i].size();
      for (int j = 0; j < v; j++)
      {
        S[i] += dist(P[i][j], P[i][(j + 1) % v]);
      }
    }
  }

  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 = p1.size(), v2 = p2.size();
    int i1 = p1[idx], i2 = p1[(idx + 1) % v1], i3 = p2[idx], i4 = p2[(idx + 1) % v2];
    return dist(i1, i4) + dist(i3, i2) - dist(i1, i2) - dist(i3, i4);
  }

  void swp(int n1, int n2, int idx)
  {
    auto &p1 = P[n1];
    auto &p2 = P[n2];
    int v1 = p1.size(), v2 = p2.size(), v = min(v1, v2);
    for (int i = idx + 1; i < v; i++)
    {
      swap(p1[i], p2[i]);
    }
    if (v1 > v2)
    {
      for (int i = v2; i < v1; i++)
        p2.push_back(p1[i]);
      for (int i = v2; i < v1; i++)
        p1.pop_back();
    }
    else if (v2 > v1)
    {
      for (int i = v1; i < v2; i++)
        p1.push_back(p2[i]);
      for (int i = v1; i < v2; i++)
        p2.pop_back();
    }
    v1 = p1.size();
    v2 = p2.size();
    S[n1] = S[n2] = 0;
    for (int i = 0; i < v1; i++)
    {
      S[n1] += dist(p1[i], p1[(i + 1) % v1]);
    }
    for (int i = 0; i < v2; i++)
    {
      S[n2] += dist(p2[i], p2[(i + 1) % v2]);
    }
  }

  int swpDiff(int n1, int n2, int idx, int len)
  {
    auto &p1 = P[n1];
    auto &p2 = P[n2];
    int v1 = p1.size(), v2 = p2.size();
    int i1 = p1[idx], i2 = p1[idx + 1], i3 = p1[idx + len], i4 = p1[idx + len + 1];
    int i5 = p2[idx], i6 = p2[idx + 1], i7 = p2[idx + len], i8 = p2[idx + len + 1];
    return dist(i1, i6) + dist(i3, i8) + dist(i5, i2) + dist(i7, i4) - dist(i1, i2) - dist(i3, i4) - dist(i5, i6) - dist(i7, i8);
  }

  void swp(int n1, int n2, int idx, int len)
  {
    auto &p1 = P[n1];
    auto &p2 = P[n2];
    int v1 = p1.size(), v2 = p2.size();
    for (int i = idx + 1; i <= idx + len; i++)
      swap(p1[i], p2[i]);
    S[n1] = S[n2] = 0;
    for (int i = 0; i < v1; i++)
    {
      S[n1] += dist(p1[i], p1[(i + 1) % v1]);
    }
    for (int i = 0; i < v2; i++)
    {
      S[n2] += 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)
  {
    auto bestP = P;
    auto bestS = S;
    auto bestScore = accumulate(all(S), 0);
    for (int n = 0; n < numLoop; n++)
    {
      int r = rnd.nextUInt(10);
      if (r < 8)
      {
        int k = rnd.nextUInt(R);
        int v = P[k].size();
        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 if (r < 9)
      {
        int r1 = rnd.nextUInt() % R;
        int r2 = rnd.nextUInt() % (R - 1);
        if (r2 >= r1)
          r2++;
        if (r1 > r2)
          swap(r1, r2);

        int v = min(P[r1].size(), P[r2].size());
        int idx = rnd.nextUInt(1, v - 1);
        int len = rnd.nextUInt(10) + 1;
        if (idx + len + 1 >= v)
        {
          len = v - idx - 2;
        }
        if (len <= 0)
          continue;

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

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

        if (-diff > temp * lrnd[n & 0xFFFF])
        {
          int pre = S[r1] + S[r2];
          swp(r1, r2, idx, len);
          int now = S[r1] + S[r2];
        }
      }
      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(P[r1].size(), P[r2].size());
        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])
        {
          int pre = S[r1] + S[r2];
          swp(r1, r2, idx);
          int now = S[r1] + S[r2];
        }
      }

      int score = accumulate(all(S), 0);
      if (score < bestScore)
      {
        bestP = P;
        bestS = S;
        bestScore = score;
      }
      //if (n % 1000000 == 0) cerr << accumulate(all(S), 0) << ": " << S << endl;
    }
    P = bestP;
    S = bestS;
    //dump(bestScore);
  }

  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(200000000);
    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, 3);
  state.getAns();

  return 0;
}


Measured memory_bytes: 11884