//#include <bits/stdc++.h>

#include <iostream>
#include <algorithm>

#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cstring>
#include <string>
#include <utility>
#include <array>
#include <complex>
#include <valarray>

#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <chrono>
#include <random>
#include <numeric>

#include<memory>


using namespace std;
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double,int> pdi;
typedef pair<long double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<29;
const ll INFLL = 1LL<<62;
const long double EPS = 1e-12;
const ll mod = 1000000000 + 7;
//const ll mod = 998244353;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const long double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod
#define inside(y, x, h, w) (0 <= (y) && (y) < (h) && 0 <= (x) && (x) < (w)) ? true : false

//debug
#define DEBUG

#define DUMPOUT cerr

#ifdef DEBUG
#define dump(...) DUMPOUT<<#__VA_ARGS__<<" :["<<__FUNCTION__<<":"<<__LINE__<<"]"<<endl; DUMPOUT<<"    "; dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif

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

//ostream
template<typename T> ostream& operator << (ostream& os, vector<T>& vec) {
    os << "["; for (int i = 0; i<vec.size(); i++) os << vec[i] << (i + 1 == vec.size() ? "" : ", "); os << "]";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

template<typename T, typename U> ostream& operator << (ostream& os, map<T, U>& map_var) {
    os << "[";
    for (auto itr = map_var.begin(); itr != map_var.end(); itr++) {
        os << "(" << itr->first << ", " << itr->second << ")"; itr++;  if(itr != map_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

template<typename T> ostream& operator << (ostream& os, set<T>& set_var) {
    os << "[";
    for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {
        os << *itr; ++itr; if(itr != set_var.end()) os << ", "; itr--;
    }
    os << "]";
    return os;
}

auto start = chrono::system_clock::now();
double timelimit = 29800;

inline bool check_time() {
    auto end = chrono::system_clock::now();
    auto dur = end - start;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    if (msec >= timelimit) return false;
    return true;
}

inline double get_time() {
  auto end = chrono::system_clock::now();
  auto dur = end - start;
  auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
  return msec;
}

inline void now_time() {
  auto end = chrono::system_clock::now();
  auto dur = end - start;
  auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
  cout << "time : " << msec << " msec"<< endl;
}

unsigned long long seed128[4]; //x,y,z,wとして利用
inline void seed(unsigned long long s){
    for(int i=1; i<=4; i++){
        seed128[i-1] = s = 1812433253U * (s^(s>>30)) + i;
    }
}

inline unsigned long long Xor128(){
  unsigned long long t;
  t=(seed128[0]^(seed128[0]<<11));
  seed128[0]=seed128[1];
  seed128[1]=seed128[2];
  seed128[2]=seed128[3];
  seed128[3]=(seed128[3]^(seed128[3]>>19))^(t^(t>>8));
  return seed128[3];
}

int n, m; //頂点数, 辺数
vector<vector<pair<int, int>>> g;
const int T = 10000;
vector<pii> order; //(id, v) ただし(-1, -1)は注文がないことを表す
int order_cnt = 0; //注文数
vector<int> start_o; //start_o[id]:= 注文idを開始した時刻
vector<vector<int>> order_info; //order_info[v]:= 頂点vの注文リスト

vector<vector<int>> d; //d[i][j]:= iからjへの最短経路距離
vector<vector<vector<int>>> path; //d[i][j]:= iからjへの最短経路path
int delivery_cnt = 0; //達成した注文数

int peak = 0;


void read() {
  //input graph
  cin >> n >> m;
  g.resize(n);
  rep(i, m) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    g[u].emplace_back(v, c);
    g[v].emplace_back(u, c);
  }
  /*
  rep(i, (int)g[0].size()) {
    cerr << g[0][i] << " ";
  }
  cerr << endl;
  exit(0);
  */
  //input order
  order_info.resize(n);
  int tmp_T;
  cin >> tmp_T;
  assert(tmp_T == T);
  rep(i, T) {
    int info;
    cin >> info;
    if (info == 0) {
      order.emplace_back(-1, -1);
      continue;
    }
    assert(info == 1);
    order_cnt++;
    int id, v;
    cin >> id >> v;
    id--; v--;
    order.emplace_back(id, v);
    start_o.push_back(i);
  }
  assert((int)start_o.size() == order_cnt);
}

void analysis() {
    //cerr << order_cnt << endl;
    //各頂点の注文数
    /*
    int region[n] = {};
    rep(i, T) {
      if (order[i].fi == -1) continue;
      region[order[i].se]++;
    }
    vector<pii> freq;
    rep(i, n) freq.emplace_back(region[i], i);
    sort(rall(freq));
    rep(i, n) {
      cerr << freq[i].se+1 << " " << freq[i].fi << endl;
    }
    */


    //注文率([-range/2, range/2]の平均)
    int range = 1000;
    vector<double> rates;
    rep2(i, range/2, T-range/2) {
      double rate = 0;
      rep2(j, i-range/2, i+range/2+1) {
        if (order[j].fi == -1) continue;
        rate++;
      }
      rate /= (double)range;
      //cout << i << " " << rate << endl;
      rates.push_back(rate);
    }
    double mx_rate = 0;
    rep(i, (int)rates.size()) {
      if (mx_rate < rates[i]) {
        mx_rate = rates[i];
        peak = i + range/2;
      }
    }
  }

vector<int> dijkstra(const int s, const int n, vector<int>& pv, const vector<vector<pii>>& g) {
  priority_queue<pii, vector<pii>, greater<pii>> que;
  vector<int> d(n, INF); d[s] = 0;
  que.emplace(0, s);
  while (!que.empty()) {
    pii p = que.top();que.pop();
    int fr = p.second;
    if (d[fr] < p.first) continue;
    for (pair<int, int> e: g[fr]) {
      int to = e.fi;
      int cost = e.se;
      if (d[to] > d[fr] + cost) {
        d[to] = d[fr] + cost;
        pv[to] = fr;
        que.emplace(d[to], to);
      }
    }
  }
  return d;

}

vector<int> get_path(int t, const vector<int>& pv) {
    vector<int> path;
    while (t != -1) {
      path.push_back(t);
      t = pv[t];
    }
    reverse(path.begin(),path.end());
    return path;
}

void calc_graph() {
  d.resize(n);
  path.resize(n);
  rep(i, n) path[i].resize(n);

  rep(i, n) {
    vector<int> pv(n, -1);
    d[i] = dijkstra(i, n, pv, g);
    rep(j, n) {
      if (i == j) continue;
      path[i][j] = get_path(j, pv);
    }
  }
}

//nowtでidの注文を完了した時に、それによって得られるスコア
double calc_value(const int nowt, const int id) {
  double wait = (nowt - start_o[id]);
  return max(0.0, (double)T*T - wait*wait);
}

void output(const vector<int>& ans) {
  rep(i, T) {
    if (ans[i] == -1) cout << ans[i] << endl;
    else cout << ans[i]+1 << endl;
  }
}

bool last_return = false;

int update_ans(double& score, int& nowt, const vector<int>& TSP_path, set<pii>& can_delivery, vector<int>& ans) {
  assert(TSP_path[0] == 0);
  if (nowt < 9500) assert(TSP_path[(int)TSP_path.size()-1] == 0);
  //rep2(i, 1, (int)TSP_path.size()-1) assert(TSP_path[i] != 0);
  vector<pii> new_order; //まだ商品を持っていないが注文は来ているid

  rep(i, (int)TSP_path.size()-1) {
    int now = TSP_path[i];
    int nx = TSP_path[i+1];
    if (nowt + d[now][nx] > T) {
      //cerr << "score : " << (ll)score << " order_cnt : " << order_cnt << " delivery_cnt : " << delivery_cnt << " delivery_rate : " << (double)delivery_cnt / order_cnt << endl;
      //output(ans);
      return i+1;
    }
    double rate = 1;
    if (nowt < peak) rate = (double)nowt/peak;
    else rate = (double)(10001-nowt) /(10001-peak);
    //int limd = 1+Xor128() % (int)(1+30*rate);
    //double limd =1+10*rate+Xor128() % 20;
    int limd = 1+Xor128()%30;
    //limd = 1+20*rate;
    //cerr << limd << " " << rate << endl;
    int limo = 100 + Xor128() % 300;
    if (nowt <= 9500 && (int)new_order.size() >= limo && d[now][0] <= limd) {
      //if (nowt >= 9500) last_return = true;
      assert(now != 0);
      //cerr << "return !" << endl;
      rep(j, (int)path[now][0].size()-1) {
        int pnow = path[now][0][j];
        int pnx = path[now][0][j+1];
        rep(k, d[pnow][pnx]) {
          ans[nowt++] = pnx;
          if (nowt == T) break;
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            can_delivery.insert(order[nowt]);
            new_order.push_back(order[nowt]);
          }
        }
        if ((int)order_info[pnx].size() != 0) {
          for (int id : order_info[pnx]) {
            delivery_cnt++;
            score += calc_value(nowt, id);
            can_delivery.erase({id, pnx});
          }
          order_info[pnx].clear();
        }
        if (nowt == T) break;
      }
      for (auto p : new_order) {
        int id = p.fi;
        int v = p.se;
        order_info[v].push_back(id);
      }
      return -1;
    }

    rep(j, d[now][nx]) {
      ans[nowt++] = nx;
      if (nowt == T) break;
      int id = order[nowt].fi;
      int v = order[nowt].se;
      if (id != -1) {
        can_delivery.insert(order[nowt]);
        new_order.push_back(order[nowt]);
      }
    }
    if ((int)order_info[nx].size() != 0) {
      for (int id : order_info[nx]) {
        delivery_cnt++;
        score += calc_value(nowt, id);
        can_delivery.erase({id, nx});
      }
      order_info[nx].clear();
    }
    if (nx == 0) {
      for (auto p : new_order) {
        int id = p.fi;
        int v = p.se;
        order_info[v].push_back(id);
      }
      new_order.clear();
      return -1;
    }
  }
  return -1;
}

const int TSP_size_limit = 0;
int dp[(1LL<<TSP_size_limit)][TSP_size_limit];

vector<pii> exact_TSP(const vector<pii>& DS) {
  //時間最小だが、評価値最小にすべき？
  vector<pii> TSP_ans;
  vector<pii> tmpDS;
  tmpDS.emplace_back(-1, 0);
  for (auto p : DS) tmpDS.push_back(p);

  int sz = (int)tmpDS.size();
  cerr << sz << endl;
  rep(i, (1LL<<TSP_size_limit))rep(j, TSP_size_limit) dp[i][j] = INF;
  dp[1][0] = 0;
  rep2(i, 1, (1LL<<sz)) {
    rep2(j, 1, sz) {
      if (i>>j&1) continue;
      rep(k, sz) {
        if (i>>k&1) {
          int fr = tmpDS[k].se;
          int to = tmpDS[j].se;
          dp[i^(1LL<<j)][j] = min(dp[i^(1LL<<j)][j], dp[i][k] + d[fr][to]);
        }
      }
    }
  }
  int mn = INF;
  int t = -1;
  rep2(j, 1, sz) {
    int fr = tmpDS[j].se;
    int to = 0;
    cerr << "cost : " << dp[(1LL<<sz)-1][j] << " j : " << tmpDS[j].se << endl;
    if (dp[(1LL<<sz)-1][j] + d[fr][to] < mn) {
      t = j;
      mn = dp[(1LL<<sz)-1][j] + d[fr][to];
    }
  }
  assert(t != -1);
  bool visited[sz] = {};
  int nowS = (1LL<<sz)-1;
  TSP_ans.emplace_back(tmpDS[0]);
  while (true) {
    TSP_ans.emplace_back(tmpDS[t]);
    int nxtS = nowS;
    nowS ^= (1LL<<t);
    bool update = false;
    rep(j, sz) {
      if (visited[j]) continue;
      int fr = tmpDS[j].se;
      int to = tmpDS[t].se;
      if (dp[nxtS][t] == dp[nowS][j] + d[fr][to]) {
        visited[j] = true;
        t = j;
        update = true;
        break;
      }
    }
    if (!update) break;
  }
  //TSP_ans.emplace_back(-1, 0);
  return TSP_ans;
}

vector<int> heulistic_TSP(const int nowt, const vector<pii>& DS) {
  set<int> VS;
  for (auto p : DS) {
    VS.insert(p.se);
  }

  vector<int> TSP_path;
  int now = 0;
  int tmp_nowt = nowt;
  TSP_path.push_back(0);
  bool visited[n] = {};
  int cnt = 0;
  while (true) {
    double mn_score = T+1;
    int nx = -1;
    for (auto v : VS) {
      if (visited[v]) continue;
      int tmpt = tmp_nowt + d[now][v];
      //if (tmpt - nowt > 10000) continue;
      double ocnt = order_info[v].size();
      /*
      double sco = 0;
      for (auto id : order_info[v]) {
        sco += calc_value(tmpt, id);
      }
      */
      double tmp_score = d[now][v];
      double low = 1500;
      double up = 1500;
      if (peak-low <= nowt && nowt <= peak+up) {
        tmp_score = d[now][v] * sqrt(d[now][v]) / (ocnt);
        //tmp_score = d[now][v] * d[now][v] * sqrt(d[now][v]) / sqrt(sco);
      }
      //double tmp_score = d[now][v];
      if (tmp_score < mn_score) {
        mn_score = tmp_score;
        nx = v;
      }
    }
    if (nx == -1) break; //TSP完了
    visited[nx] = true;
    bool via_store = false;
    rep2(i, 1, (int)path[now][nx].size()) {
      if (path[now][nx][i] == 0) {
        via_store = true;
        break;
      }
    }
    if (via_store) {
      TSP_path.push_back(0);
      return TSP_path;
    }
    TSP_path.push_back(nx);
    tmp_nowt += d[now][nx];
    now = nx;
    cnt++;
    //if (cnt == 1000) break;
  }
  /*
  vector<int> v;
  for (int x : VS) {
    v.push_back(x);
  }
  vector<pair<double, int>> score_v;
  for (int x : v) {
    double score = 0;
    for (int id : order_info[x]) {
      score += calc_value(nowt, id);
    }
    score_v.emplace_back(score, x);
  }
  sort(rall(score_v));
  rep(i, (int)score_v.size()) cerr << score_v[i].fi << endl;
  int limit = 3000;
  rep(i, min(limit, (int)score_v.size())) {
    int v = score_v[i].se;
    TSP_path.push_back(v);
  }
  */
  //if (nowt >= 9500) return TSP_path;
  TSP_path.push_back(0);
  return TSP_path;
}

//最小単位で表現 (u->vをu->w->v)
vector<int> trans_minimum(const vector<int> TSP) {
  vector<int> ret;
  rep(i, (int)TSP.size()-1) {
    int now = TSP[i];
    int nx = TSP[i+1];
    rep(j, (int)path[now][nx].size()-1) {
      ret.push_back(path[now][nx][j]);
    }
    if (i == (int)TSP.size() - 2) {
      ret.push_back(0);
    }
  }
  return ret;
}

double sim(int nowt, const vector<int>& TSP_path) {
  double t = 0;
  double score = 0;
  vector<int> min_path = trans_minimum(TSP_path);
  /*
  rep(i, (int)min_path.size()-1) {
    int now = min_path[i];
    int nx = min_path[i+1];
    t += d[now][nx];
  }
  return t;
  if (nowt < 9500) return t;
  */
  //if (nowt < peak-500 || peak+500 < nowt) return t;
  int pret = nowt+1;
  vector<vector<int>> tmp_order_info = order_info;
  rep(i, (int)min_path.size()-1) {
    int now = min_path[i];
    int nx = min_path[i+1];
    if (nowt + d[now][nx] > T) return -score;
    nowt += d[now][nx];
    t += d[now][nx];
    if ((int)tmp_order_info[nx].size() != 0) {
      rep(j, (int)tmp_order_info[nx].size()) {
        int id = tmp_order_info[nx][j];
        score += calc_value(nowt, id);
      }
      tmp_order_info[nx].clear();
    }
    //修正
    if (nx == 0) {
      //return -score;
      while (pret <= nowt) {
        int id = order[pret].fi;
        int v = order[pret].se;
        if (id != -1) {
          tmp_order_info[v].push_back(id);
        }
        pret++;
      }
      //return -score/t;
    }
  }
  //return t;
  //cerr << score << " " << t << endl;
  return -score;

}

double opt2_SA(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  /*
  double diff_score = d[TSP_path[u-1]][TSP_path[u]] + d[TSP_path[v]][TSP_path[v+1]];
  Score -= diff_score;
  diff_score = d[TSP_path[u-1]][TSP_path[v]] + d[TSP_path[u]][TSP_path[v+1]];
  Score += diff_score;
  */
  reverse(TSP_path.begin()+u, TSP_path.begin()+v+1);
  //TODO: 高速化
  return sim(nowt, TSP_path);
}

double swap_2(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  swap(TSP_path[u], TSP_path[v]);
  return sim(nowt, TSP_path);
}

double insert(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int u = -1;
  int v = -1;
  int sz = TSP_path.size();
  int s = 0;
  int t = sz-1;
  int loop = 0;
  int limit_loop = 1000;
  while (loop < limit_loop && (u == v || u == s || v == t)) {
    loop++;
    u = Xor128() % sz;
    v = Xor128() % sz;
    if (u > v) swap(u, v);
  }
  if (loop == limit_loop) return INF;
  int iv = TSP_path[v];
  TSP_path.erase(TSP_path.begin()+v);
  TSP_path.insert(TSP_path.begin()+u, iv);
  return sim(nowt, TSP_path);
}

double or_opt(int nowt, vector<int>& TSP_path) {
  if (TSP_path.size() == 2) return INF;
  int len = 1+Xor128() % min((int)TSP_path.size()-2, 3);
  int l = Xor128() % TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (l == 0 || l+len-1 >= (int)TSP_path.size()-1)) {
    loop++;
    l = Xor128() % TSP_path.size();
  }
  if (loop == limit) return INF;
  vector<int> tmp;
  vector<int> insP;
  rep(i, (int)TSP_path.size()) {
    if (l <= i && i < l + len)  {
      insP.push_back(TSP_path[i]);
    }
    else {
      tmp.push_back(TSP_path[i]);
    }
  }
  int ins = Xor128() % (int)tmp.size();
  loop = 0;
  while (loop < limit && (ins == 0 || ins == (int)tmp.size()-1)) {
    loop++;
    ins = Xor128() % (int) tmp.size();
  }
  if (loop == limit) return INF;
  for (auto x : insP) {
    tmp.insert(tmp.begin()+ins, x);
    ins++;
  }
  double ret = sim(nowt, tmp);
  //cerr << ret << endl;
  return ret;
}

double remove(int nowt, vector<int>& TSP_path, vector<int>& removed) {
  if ((int)TSP_path.size() == 2) return INF;
  int r = Xor128() % (int)TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (r == 0 || r == (int)TSP_path.size()-1)) {
    loop++;
    r = Xor128() % (int)TSP_path.size();
  }
  if (loop == limit) return INF;
  int rv = TSP_path[r];
  TSP_path.erase(TSP_path.begin()+r);
  removed.push_back(rv);
  return sim(nowt, TSP_path);
}

double add(int nowt, vector<int>& TSP_path, vector<int>& removed) {
  if ((int)removed.size() == 0) return INF;
  int a = Xor128() % (int)removed.size();
  int av = removed[a];
  removed.erase(removed.begin()+a);
  int ins = Xor128() % (int)TSP_path.size();
  int loop = 0;
  int limit = 1000;
  while (loop < limit && (ins == 0 || ins == ((int)TSP_path.size()-1))) {
    loop++;
    ins = Xor128() % TSP_path.size();
  }
  if (loop == limit) return INF;
  TSP_path.insert(TSP_path.begin()+ins, av);
  return sim(nowt, TSP_path);
}

double NeighborSearch(int nowt, vector<int>& TSP_path, vector<int>& removed) {
  int id = Xor128() % 2;
  if (id == 0) return opt2_SA(nowt, TSP_path);
  else if (id == 1) return or_opt(nowt, TSP_path);
  //else if (id == 2) return swap_2(nowt, TSP_path);
  //else if (id == 3) return remove(nowt, TSP_path, removed);
  //else if (id == 4) return add(nowt, TSP_path, removed);
  //else if (id == 1) return insert(nowt, TSP_path);
  //else if (id == 1) return oropt_SA(TSP_path);
}

vector<int> SA(const int nowt, const vector<int>& TSP_path) {
  //construct TSP_path
  assert(TSP_path[0] == 0);
  if (nowt < 9500) assert(TSP_path[(int)TSP_path.size()-1] == 0);
  rep2(i, 1, (int)TSP_path.size()-1) {
    assert(TSP_path[i] != 0);
  }
  /*
  rep(i, (int)TSP_ans.size()-1) {
    int now = TSP_ans[i].se;
    int nx = TSP_ans[i+1].se;
    rep(j, (int)path[now][nx].size()-1) {
      int pnow = path[now][nx][j];
      TSP_path.push_back(pnow);
    }
    tmp_nowt += d[now][nx];
    if (i+1 == (int)TSP_ans.size()-1) {
      assert(TSP_ans[i+1].se == 0);
      TSP_path.push_back(0);
    }
  }
  */
  //cerr << TSP_path.size() << endl;
  if (TSP_path.size() <= 10) return TSP_path;
  vector<int> tmp_TSP_path = TSP_path;
  //tmp_TSP_path = trans_minimum(tmp_TSP_path);
  /*
  cerr << tmp_TSP_path.size() << endl;
  bool used[n] = {};
  vector<int> uni_path = {0};
  used[0] = true;
  rep(i, (int)tmp_TSP_path.size()) {
    int v = tmp_TSP_path[i];
    if (used[v]) continue;
    uni_path.push_back(v);
    used[v] = true;
  }
  uni_path.push_back(0);
  cerr << uni_path.size() << endl;
  */
  //start SA;
  //double limit_time = 3000 * (double)tmp_TSP_path.size()/300;
  double limit_time = 100;

  double bestScore = sim(nowt, tmp_TSP_path);
  vector<int> bestPath = tmp_TSP_path;
  vector<int> best_removed;

  double curScore = bestScore;
  vector<int> curPath = tmp_TSP_path;
  vector<int> cur_removed;


  int R = INF;
  int loop = 0;
  double preScore = curScore;
  //cerr << "before Score : " << (ll)curScore << " path size : " << tmp_TSP_path.size() << endl;
  rep(_, 1) {
    double startTemp = 1000000;
    //if (peak - 500 <= nowt && nowt <= peak+500) startTemp = 10000;
    //if (nowt >= 9500) startTemp = 1000;
    double endTemp = 0;
    double st_time = get_time();
    //cerr << "SA loop : " <<  _ << endl;
    while (true) {
      if (!check_time()) return bestPath;
      loop++;
      //cerr << loop << endl;
      double t = get_time() - st_time;
      double temp = startTemp + (endTemp - startTemp) * t / limit_time;
      if (temp <= 0) break;
      vector<int> nextPath = curPath;
      vector<int> next_removed = cur_removed;
      /*
      pair<int, int> p = opt2_SA(nextScore, curPath);
      if (p.fi == -1 && p.se == -1) break;
      */
      double nextScore = NeighborSearch(nowt, nextPath, next_removed);
      double prob = exp((curScore - nextScore) / temp);
      bool FORCE = prob > (double)(Xor128() % R) / R;
      //bool FORCE = (curScore > nextScore);
      if (FORCE) {
        curScore = nextScore;
        curPath = nextPath;
        cur_removed = next_removed;
        if (curScore < bestScore) {
          bestScore = curScore;
          bestPath = curPath;
          best_removed = cur_removed;
        }
      }
      if (loop % 1000 == 0) {
        //cerr << "loop : " << loop << " curScore : " << (ll)curScore << " bestScore : " <<  (ll)bestScore << " temp :"<< temp << endl;
      }
    }
  }
  //cerr << "after Score :  " << (ll)bestScore << endl;
  cerr << "diff score : " << (ll)preScore-(ll)bestScore << endl;
  cerr << "-----------" << endl;
  return bestPath;
}



pair<bool, int> delivery(double& score, int& nowt, set<pii>& can_delivery, vector<int>& ans, vector<vector<int>>& TSPS) {
  vector<pii> DS; //DS:Sの部分集合, Sのうち今から配達する頂点集合(すべて配達するのが高スコアの必要条件そう)
  for (auto p : can_delivery) {
    DS.emplace_back(p);
  }
  vector<pii> TSP_ans;
  vector<int> TSP_path;
  vector<int> best_TSP_path;
  if (DS.size() < TSP_size_limit) {
    //cerr << "exact_TSP" << endl;
    TSP_ans = exact_TSP(DS);
    if ((int)TSP_ans.size() == 2) return {false, -1};
  }
  else {
    //cerr << "heulistic_TSP" << endl;
    TSP_path = heulistic_TSP(nowt, DS);
    if ((int)TSP_path.size() == 2) return {false, -1};
    //best_TSP_path = SA(nowt, TSP_path);
    best_TSP_path = TSP_path;
    best_TSP_path = trans_minimum(best_TSP_path);
    if ((int)best_TSP_path.size() <= 2) return {false, -1};
  }
  int val = update_ans(score, nowt, best_TSP_path, can_delivery, ans);
  if (val != -1) {
    vector<int> next_TSP_path;
    rep(i, val) {
      next_TSP_path.push_back(best_TSP_path[i]);
    }
    TSPS.push_back(next_TSP_path);
    return {true, 0};
  }
  else TSPS.push_back(best_TSP_path);
  return {true, -1};
}


vector<int> solve() {
  double best_score = 0;
  vector<int> best_ans;
  vector<vector<int>> best_TSPS;
  timelimit = 29800;
  while (check_time()) {
    double score = 0;
    int nowt = 0;
    vector<int> ans(T, -1);
    set<pii> can_delivery;
    vector<vector<int>> TSPS;
    delivery_cnt = 0;
    rep(i, n) order_info[i].clear();

    while (nowt < T) {
      while (nowt < T && (int)can_delivery.size() == 0) {
        int id = order[nowt].fi;
        int v = order[nowt].se;
        if (id != -1) {
          can_delivery.insert(order[nowt]);
          order_info[v].push_back(id);
          break;
        }
        nowt++;
      }
      if (nowt == T) break;
      //cerr << "will deliver " << nowt << endl;
      pair<bool, int> pp = delivery(score, nowt, can_delivery, ans, TSPS);
      bool update = pp.fi;
      int val = pp.se;
      if (val == 0) break;
      //cerr << "[now time] : " << nowt << " [delivery] : " << can_delivery.size() << endl;
      //peak付近でちょっと待つ
      /*
      double wait = Xor128() % 100;
      while (nowt < T && peak-wait <= nowt && nowt <= peak+wait) {
        nowt++;
        if (nowt >= T) break;
        int id = order[nowt].fi;
        int v = order[nowt].se;
        if (id != -1) {
          can_delivery.insert(order[nowt]);
          order_info[v].push_back(id);
        }
      }
      */
      if (!update) {
        nowt++;
        while (nowt < T) {
          int id = order[nowt].fi;
          int v = order[nowt].se;
          if (id != -1) {
            can_delivery.insert(order[nowt]);
            order_info[v].push_back(id);
            break;
          }
          nowt++;
        }
      }
    }
    //cerr << "score : " << (ll)score <<  " best_score : " << (ll)best_score << " order_cnt : " << order_cnt << " delivery_cnt : " << delivery_cnt << " delivery_rate : " << (double)delivery_cnt / order_cnt << endl;
    if (best_score < score) {
      best_score = score;
      best_ans = ans;
      best_TSPS = TSPS;
    }
  }
  /*
  rep(i, best_TSPS.size()) {
    rep(j, best_TSPS[i].size()) cerr << best_TSPS[i][j] << " ";
    cerr << endl;
    cerr << "-----------------------------------------------" << endl;
  }
  */
  /*
  timelimit = 29800;
  while(check_time()) {

  }
  */
  return best_ans;
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  seed(37);
  read();
  analysis();
  //cerr << "peak : " << peak << endl;
  //cerr << "read passed" << endl;
  calc_graph();
  //cerr << "calc_graph passed" << endl;
  //analysis();
  vector<int> ans = solve();
  //cerr << "solve passed" << endl;
  output(ans);
}


Measured memory_bytes: 23796