#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;
 
const double eps = 1e-7;
#define Loop(i, n) for(int i = 0; i < int(n); i++)
#define Loopll(i, n) for(ll i = 0; i < ll(n); i++)
#define Loop1(i, n) for(int i = 1; i <= int(n); i++)
#define Loopll1(i, n) for(ll i = 1; i <= ll(n); i++)
#define Loopr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = ll(n) - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = int(n); i >= 1; i--)
#define Looprll1(i, n) for(ll i = ll(n); i >= 1; i--)
#define Foreach(buf, container) for(const auto &buf : container)
#define Loopdiag(i, j, h, w, sum) for(int i = ((sum) >= (h) ? (h) - 1 : (sum)), j = (sum) - i; i >= 0 && j < (w); i--, j++)
#define Loopdiagr(i, j, h, w, sum) for(int j = ((sum) >= (w) ? (w) - 1 : (sum)), i = (sum) - j; j >= 0 && i < (h); j--, i++)
#define Loopdiagsym(i, j, h, w, gap) for (int i = ((gap) >= 0 ? (gap) : 0), j = i - (gap); i < (h) && j < (w); i++, j++)
#define Loopdiagsymr(i, j, h, w, gap) for (int i = ((gap) > (h) - (w) - 1 ? (h) - 1 : (w) - 1 + (gap)), j = i - (gap); i >= 0 && j >= 0; i--, j--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(ex_i, vector.size()) { cout << vector[ex_i] << " "; } cout << endl;
#define printmx(matrix) Loop(ex_i, matrix.size()) { Loop(ex_j, matrix[ex_i].size()) { cout << matrix[ex_i][ex_j] << " "; } cout << endl; }
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
#define Comp(type_t) bool operator<(const type_t &another) const
#define fst first
#define snd second
#define INF INFINITY
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) { Foreach(x, xs) if (!(x >= 0 && x < t)) return false; return true; }
int ceillog2(ll x) { int ret = 0;	x--; while (x > 0) { ret++; x >>= 1; } return ret; }
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (m * m <= x ? 0 : -1); }
ll ceilsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (x <= m * m ? 0 : 1); }
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); }
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }
 
//========================================================================//
 
class Timestamp {
private:
	enum timestamp_t {
		BEGIN, END, PAUSE
	};
	std::chrono::system_clock::time_point start, finish;
	timestamp_t mode;
	double elapsed;
public:
	Timestamp() {
		mode = END;
		elapsed = 0;
	}
	void begin() {
		if (mode == BEGIN) {
			std::cout << "timestamp mode error with BEGIN -> BEGIN" << std::endl;
			exit(EXIT_SUCCESS);
		}
		mode = BEGIN;
		start = std::chrono::system_clock::now();
	}
	void pause() {
		finish = std::chrono::system_clock::now();
		if (mode == PAUSE) {
			std::cout << "timestamp mode error with PAUSE -> PAUSE" << std::endl;
			exit(EXIT_SUCCESS);
		}
		if (mode == END) {
			std::cout << "timestamp mode error with END -> PAUSE" << std::endl;
			exit(EXIT_SUCCESS);
		}
		elapsed += double(std::chrono::duration_cast<std::chrono::nanoseconds>(finish - start).count());
		mode = PAUSE;
	}
	double end() {
		finish = std::chrono::system_clock::now();
		double ret = 0;
		if (mode == END) {
			std::cout << "timestamp mode error with END -> END" << std::endl;
			exit(EXIT_SUCCESS);
		}
		if (mode == PAUSE) {
			ret = elapsed / 1e6;
			elapsed = 0;
		}
		else {
			elapsed += double(std::chrono::duration_cast<std::chrono::nanoseconds>(finish - start).count());
			ret = elapsed / 1e6;
			elapsed = 0;
		}
		mode = END;
		return ret;
	}
	double check() {
		if (mode == BEGIN) {
			std::chrono::system_clock::time_point cur = std::chrono::system_clock::now();
			return double(std::chrono::duration_cast<std::chrono::nanoseconds>(cur - start).count()) / 1e6;
		}
		else {
			return elapsed / 1e6;
		}
	}
};
 
void Warshallfloyd(vvi &table, vvi &route) {
	int n = int(table.size());
	Loop(i, n) table[i][i] = 0;
	route = vvi(n, vi(n));
	Loop(i, n) {
		Loop(j, n) {
			route[i][j] = j;
		}
	}
	Loop(k, n) {
		Loop(i, n) {
			Loop(j, n) {
				if (table[i][k] == INT_MAX || table[k][j] == INT_MAX) continue;
				if (table[i][k] + table[k][j] < table[i][j]) {
					table[i][j] = table[i][k] + table[k][j];
					route[i][j] = route[i][k];
				}
			}
		}
	}
}
 
class Random_Real {
private:
	mt19937 *mt;
    uniform_real_distribution<> *distr_real;
public:
	Random_Real() {
		mt = new mt19937(unsigned(time(NULL)));
		distr_real = new uniform_real_distribution<>(0, 1);
	}
    double get() {
        return (*distr_real)(*mt);
    }
	double get_inrange(double l, double r) {
		double rx = this->get();
		return l * (1 - rx) + r * rx;
	}
};
 
Random_Real *rr = new Random_Real();
 
ll twice(ll x) {
	return x * x;
}
 
//========================================================================//
 
struct node_t {
	int id;
	vi nbrs;
	vi eids;
};
 
struct edge_t {
	int id;
	int s, t;
	int d;
};
 
struct graph_t {
	int n, m;
	vector<node_t> nodes;
	vector<edge_t> edges;
	vvi table;
	vvi route;
	vi dst_seq; // nearest nodes from shop
};
 
struct order_t {
	int id;
	int dst_nid;
	int ord_time;
};
 
struct orderlist_t {
	int T_max;
	int T_last;
	vector<vector<order_t>> orders;
};
 
struct localtime_t {
	int cur = 0;
	int rem = 0;
	int lastput = 0;
};
 
struct initparam_t {
	size_t SAVE_NUM = 1;
	int ALTERNATIVE_INTERVAL = 1;
	int SHORT_SPAN = 1;
	int LONG_SPAN = 1;
	int QUICK_START = 1;
	Comp(initparam_t) {
		ll a = (ll(SAVE_NUM) << 50) + (ll(ALTERNATIVE_INTERVAL) << 45) + (ll(SHORT_SPAN) << 30) + (ll(LONG_SPAN) << 10) + ll(QUICK_START);
		ll b = (ll(another.SAVE_NUM) << 50) + (ll(ALTERNATIVE_INTERVAL) << 45) 
		+ (ll(another.SHORT_SPAN) << 30) + (ll(another.LONG_SPAN) << 10) + ll(another.QUICK_START);
		return a < b;
	}
};
 
namespace Trie {
 
	struct trienode_t {
		int val; int val_sum; unordered_map<int, trienode_t*> childs_mp; int deg; trienode_t *parent_node;
		vi local_cmds; vector<order_t> rem_ords; ll score_sum; int alternative_counter;
		int branched_flag = 0; initparam_t param;
	};
 
	trienode_t *root;
 
	void init_trie() {
		root = new trienode_t;
		root->val = 0;
		root->val_sum = 0;
		root->deg = 0;
		root->parent_node = nullptr;
		root->score_sum = 0;
		root->alternative_counter = 0;
		root->branched_flag = 0;
	}
 
	// vals[0, last_id) exists, and return the last node
	void find_prefix(const vi &vals, trienode_t *last_node, int &last_id) {
		last_node = root;
		for (; last_id < int(vals.size()); ++last_id) {
			int v = vals[last_id];
			auto itr = last_node->childs_mp.find(v);
			if (itr == last_node->childs_mp.end()) {
				return;
			}
			else {
				last_node = itr->second;
			}
		}
	}
	trienode_t* add(trienode_t *parent_node, const int val, const vi &local_cmds, const vector<order_t> &rem_ords, const ll score_sum, const int alternative_counter, const initparam_t &param) {
		if (parent_node->childs_mp.find(val) != parent_node->childs_mp.end()) return nullptr;
		parent_node->childs_mp[val] = new trienode_t;
		trienode_t *ret_node = parent_node->childs_mp[val];
		ret_node->val = val;
		ret_node->val_sum = parent_node->val_sum + val;
		ret_node->deg = parent_node->deg + 1;
		ret_node->parent_node = parent_node;
		ret_node->local_cmds = local_cmds;
		ret_node->rem_ords = rem_ords;
		ret_node->score_sum = score_sum;
		ret_node->alternative_counter = alternative_counter;
		ret_node->param = param;
		return ret_node;
	}
	void erase(trienode_t *node) {
		if (node == root) return;
		Loopitr(itr, node->childs_mp) {
			erase(itr->second);
		}
		node->parent_node->childs_mp.erase(node->val);
		delete(node);
	}
};
 
//========================================================================//
 
void input(graph_t &G, orderlist_t &ordlst) {
 
	cin >> G.n >> G.m;
	G.nodes.resize(G.n);
	Loop(i, G.n) {
		G.nodes[i].id = i;
	}
	G.edges.resize(G.m);
	Loop(i, G.m) {
		G.edges[i].id = i;
	}
	G.table = vvi(G.n, vi(G.n, INT_MAX));
	Loop(i, G.m) {
		int s, t; cin >> s >> t; s--; t--;
		int d; cin >> d;
		G.edges[i].s = s;
		G.edges[i].t = t;
		G.edges[i].d = d;
		G.nodes[s].nbrs.push_back(t);
		G.nodes[s].eids.push_back(i);
		G.nodes[t].nbrs.push_back(s);
		G.nodes[t].eids.push_back(i);
		G.table[s][t] = d;
		G.table[t][s] = d;
	}
	Warshallfloyd(G.table, G.route);
	vector<pair<int, int>> dst_seq(G.n - 1);
	Loop(i, G.n - 1) {
		dst_seq[i] = {G.table[0][i + 1], i + 1};
	}
	sort(dst_seq.begin(), dst_seq.end());
	G.dst_seq = vi(G.n - 1);
	Loop(i, G.n - 1) {
		G.dst_seq[i] = dst_seq[i].snd;
	}
	cin >> ordlst.T_max;
	ordlst.orders.resize(ordlst.T_max);
	Loop(i, ordlst.T_max) {
		int N_new; cin >> N_new;
		Loop(_, N_new) {
			order_t order;
			cin >> order.id;
			cin >> order.dst_nid; order.dst_nid--;
			order.ord_time = i;
			ordlst.orders[i].push_back(order);
			ordlst.T_last = i;
		}
	}
}
 
void output(const vector<int> &cmds) {
	Loop(i, cmds.size()) {
		cout << cmds[i] << endl;
	}
}
 
Timestamp ts;
 
//
 
void heuristic_master(const graph_t &G, const orderlist_t &ordlst, vector<int> &ans);
ll solve_mid_localstep(const graph_t &G, const orderlist_t &ordlst, vector<order_t> &ords, vector<int> &cmds, localtime_t &T);
ll solve_last_localstep(const graph_t &G, const orderlist_t &ordlst, vector<order_t> &ords, vector<int> &cmds, localtime_t &T);
 
//
 
int main() {
 
	quickio();
 
	ts.begin();
 
	graph_t G;
	orderlist_t ordlst;
	vector<int> ans;
	Trie::init_trie();
 
	input(G, ordlst);
 
	heuristic_master(G, ordlst, ans);
	output(ans);
 
}
 
//========================================================================//
 
Trie::trienode_t* solve_core(const graph_t &G, const orderlist_t &ordlst, const initparam_t &param, Trie::trienode_t *trie_ptr) {
	localtime_t T;
	T.cur = trie_ptr->val_sum;
	T.lastput = T.cur;
	vector<order_t> rem_ords = trie_ptr->rem_ords;
	ll score_sum = trie_ptr->score_sum;
	int alternative_counter = trie_ptr->alternative_counter;
	bool waiting_for_last_ord = false;
	for (; T.cur < ordlst.T_max;) {
		if (T.cur >= ordlst.T_last) {
			T.rem = ordlst.T_max - T.cur;
			vector<int> cmds;
			localtime_t T_bckup = T;
			score_sum += solve_last_localstep(G, ordlst, rem_ords, cmds, T);
			int dT = T.cur - T_bckup.cur;
			trie_ptr = Trie::add(trie_ptr, dT, cmds, rem_ords, score_sum, alternative_counter, param);
		}
		else if (rem_ords.size() < param.SAVE_NUM) {
			localtime_t T_bckup = T;
			for (int xt = T.cur + 1; xt <= ordlst.T_last && rem_ords.size() < param.SAVE_NUM; ++xt) {
				Foreach(ord, ordlst.orders[xt]) {
					rem_ords.push_back(ord);
				}
				T.lastput = xt;
			}
			T.cur = T.lastput;
			int dT = T.cur - T_bckup.cur;
			trie_ptr = Trie::add(trie_ptr, dT, { -dT }, rem_ords, score_sum, alternative_counter, param);
		}
		else if (waiting_for_last_ord) {
			localtime_t T_bckup = T;
			for (int xt = T.cur + 1; xt <= ordlst.T_last; ++xt) {
				Foreach(ord, ordlst.orders[xt]) {
					rem_ords.push_back(ord);
				}
				T.lastput = xt;
			}
			T.cur = T.lastput;
			int dT = T.cur - T_bckup.cur;
			trie_ptr = Trie::add(trie_ptr, dT, { -dT }, rem_ords, score_sum, alternative_counter, param);
			waiting_for_last_ord = false;
		}
		else {
			alternative_counter += 1;
			if (param.QUICK_START < 10 && rem_ords.size() <= param.SAVE_NUM) {
				T.rem = int(rem_ords.size()) * param.QUICK_START;
			}
			else if (param.LONG_SPAN < 500 && 4500 <= T.cur && T.cur < 5000) {
				T.rem = 500;
			}
			else if (T.cur < ordlst.T_last - param.LONG_SPAN) {
				if (alternative_counter % param.ALTERNATIVE_INTERVAL == 0) T.rem = param.LONG_SPAN;
				else T.rem = param.SHORT_SPAN;
			}
			else {
				T.rem = ordlst.T_last - T.cur;
				waiting_for_last_ord = true;
			}
			vector<int> cmds;
			localtime_t T_bckup = T;
			score_sum += solve_mid_localstep(G, ordlst, rem_ords, cmds, T);
			int dT = T.cur - T_bckup.cur;
			if (dT > 0) {
				trie_ptr = Trie::add(trie_ptr, dT, cmds, rem_ords, score_sum, alternative_counter, param);
			}
			else {
				for (int xt = T.cur + 1; xt <= ordlst.T_last; ++xt) {
					Foreach(ord, ordlst.orders[xt]) {
						rem_ords.push_back(ord);
					}
					T.lastput = xt;
					if (ordlst.orders[xt].size()) break;
				}
				T.cur = T.lastput;
				int dT = T.cur - T_bckup.cur;
				trie_ptr = Trie::add(trie_ptr, dT, { -dT }, rem_ords, score_sum, alternative_counter, param);
			}
		}
		if (trie_ptr == nullptr) return trie_ptr;
	}
	return trie_ptr;
}
 
vector<int> get_ans(const graph_t &G, Trie::trienode_t* node) {
	vector<int> ans;
	stack<int> stk;
	while (node != Trie::root) {
		Loopr(i, node->local_cmds.size()) {
			stk.push(node->local_cmds[i]);
		}
		node = node->parent_node;
	}
	int cur_nid = 0;
	while (stk.size()) {
		int x = stk.top(); stk.pop();
		if (x < 0) {
			Loop(_, -x) {
				ans.push_back(-1);
			}
		}
		else {
			while (cur_nid != x) {
				int next_nid = G.route[cur_nid][x];
				Loop(_, G.table[cur_nid][next_nid]) {
					ans.push_back(next_nid + 1);
				}
				cur_nid = next_nid;
			}
		}
	}
	return ans;
}
 
void local_search(const graph_t &G, const orderlist_t &ordlst, Trie::trienode_t* trie_ptr, set<pair<ll, Trie::trienode_t*>> &solution_set) {
	set<initparam_t> param_set;
	for (int alternative_interval = 1; alternative_interval <= 5; alternative_interval += 1) {
		if (alternative_interval == trie_ptr->param.ALTERNATIVE_INTERVAL) continue;
		initparam_t param = trie_ptr->param;
		param.ALTERNATIVE_INTERVAL = alternative_interval;
		param_set.insert(param);
	}
	if (trie_ptr->param.ALTERNATIVE_INTERVAL > 1) {
		for (int short_span = max(10, trie_ptr->param.SHORT_SPAN - 75); short_span <= trie_ptr->param.SHORT_SPAN + 75; short_span += 5) {
			if (short_span == trie_ptr->param.SHORT_SPAN) continue;
			initparam_t param = trie_ptr->param;
			param.SHORT_SPAN = short_span;
			param_set.insert(param);
		}
	}
	for (int long_span = max(250, trie_ptr->param.LONG_SPAN - 300); long_span <= max(250, trie_ptr->param.LONG_SPAN + 300); long_span += 30) {
		if (long_span == trie_ptr->param.LONG_SPAN) continue;
		initparam_t param = trie_ptr->param;
		param.LONG_SPAN = long_span;
		param_set.insert(param);
	}
	Foreach(param, param_set) {
		if (ts.check() >= 28500.0) break;
		Trie::trienode_t *trie_ptr_buf = trie_ptr;
		Trie::trienode_t* trie_ptr_res = solve_core(G, ordlst, param, trie_ptr_buf);
		if (trie_ptr_res != nullptr) solution_set.insert({ trie_ptr_res->score_sum, trie_ptr_res });
	}
	trie_ptr->branched_flag = 1;
}
 
void init_search(const graph_t &G, const orderlist_t &ordlst, set<pair<ll, Trie::trienode_t*>> &solution_set) {
	set<initparam_t> param_set;
	// frequent in short range
	Foreach(save_num, vi({5, 8, 12, 15})) {
		Foreach(alternative_interval, vi({1, 2, 3})) {
			Foreach(short_span, vi({30, 50, 75, 100})) {
				if (alternative_interval == 1 && short_span != 30) continue;
				Foreach(long_span, vi({300, 400, 500, 600, 700, 900, 1000, 1200})) {
					Foreach(quick_start, vi({5, 7})) {
						if (quick_start * save_num > short_span) continue;
						initparam_t param;
						param.SAVE_NUM = save_num;
						param.ALTERNATIVE_INTERVAL = alternative_interval;
						param.SHORT_SPAN = short_span;
						param.LONG_SPAN = long_span;
						param.QUICK_START = quick_start;
						param_set.insert(param);
					}
				}
			}
		}
	}
	// frequent in mid range
	Foreach(save_num, vi({6, 12, 18, 24, 30})) {
		Foreach(alternative_interval, vi({1, 2})) {
			Foreach(short_span, vi({50, 75, 100, 125, 150})) {
				if (alternative_interval == 1 && short_span > 50) continue;
				Foreach(long_span, vi({500, 600, 700, 900, 1000, 1200})) {
					Foreach(quick_start, vi({7, 10})) {
						if (quick_start * save_num > short_span) continue;
						initparam_t param;
						param.SAVE_NUM = save_num;
						param.ALTERNATIVE_INTERVAL = alternative_interval;
						param.SHORT_SPAN = short_span;
						param.LONG_SPAN = long_span;
						param.QUICK_START = quick_start;
						param_set.insert(param);
					}
				}
			}
		}
	}
	// frequent in wide range
	Foreach(save_num, vi({10, 15, 20, 25, 30})) {
		Foreach(alternative_interval, vi({1, 2})) {
			Foreach(short_span, vi({100, 125, 150, 200})) {
				if (alternative_interval == 1 && short_span > 100) continue;
				Foreach(long_span, vi({600, 700, 900, 1000, 1200})) {
					Foreach(quick_start, vi({7, 10})) {
						if (quick_start * save_num > short_span) continue;
						initparam_t param;
						param.SAVE_NUM = save_num;
						param.ALTERNATIVE_INTERVAL = alternative_interval;
						param.SHORT_SPAN = short_span;
						param.LONG_SPAN = long_span;
						param.QUICK_START = quick_start;
						param_set.insert(param);
					}
				}
			}
		}
	}
	Foreach(param, param_set) {
		Trie::trienode_t* trie_ptr = solve_core(G, ordlst, param, Trie::root);
		if (trie_ptr != nullptr) solution_set.insert({trie_ptr->score_sum, trie_ptr});
	}
}
 
// Search step1: master program of heuristics
void heuristic_master(const graph_t &G, const orderlist_t &ordlst, vector<int> &ans) {
	Trie::root->rem_ords = ordlst.orders[0];
	set<pair<ll, Trie::trienode_t*>> solution_set;
	init_search(G, ordlst, solution_set);
	Trie::trienode_t* best_leaf = solution_set.rbegin()->snd;
	Trie::root->param = best_leaf->param;
	while (ts.check() < 28500.0) {
		bool found_better = false;
		vector<Trie::trienode_t*> trace;
		Trie::trienode_t* focus = best_leaf;
		do {
			if (focus != best_leaf && focus != best_leaf->parent_node) {
				trace.push_back(focus);
			}
			focus = focus->parent_node;
		} while (focus != nullptr && !focus->branched_flag);
		Loopr(i, trace.size()) {
			if (trace[i]->val <= 10) continue;
			if (ts.check() >= 28500.0) break;
			local_search(G, ordlst, trace[i], solution_set);
			trace[i]->branched_flag = 1;
			if (solution_set.rbegin()->snd != best_leaf) {
				found_better = true;
				best_leaf = solution_set.rbegin()->snd;
				break;
			} 
		}
		if (!found_better) {
			auto itr = solution_set.find({best_leaf->score_sum, best_leaf});
			if (itr == solution_set.begin()) break;
			else {
				itr--;
				best_leaf = itr->snd;
			}
		}
	}
	ans = get_ans(G, solution_set.rbegin()->snd);
}
 
ll move_next(const graph_t &G, const orderlist_t &ordlst, int &cur_nid, int dst_nid, vector<vector<order_t>> &ords_per_dst, vector<int> &cmds, localtime_t &T) {
	const ll T_max2 = twice(ordlst.T_max);
	ll score = 0;
	while (cur_nid != dst_nid) {
		int next_nid = G.route[cur_nid][dst_nid];
		T.cur += G.table[cur_nid][next_nid];
		T.rem -= G.table[cur_nid][next_nid];
		if (next_nid == 0) {
			for (int xt = T.lastput + 1; xt <= T.cur; ++xt) {
				Foreach(ord, ordlst.orders[xt]) {
					ords_per_dst[ord.dst_nid].push_back(ord);
				}
			}
			T.lastput = T.cur;
			cmds.push_back(next_nid);
		}
		else if (ords_per_dst[next_nid].size()) {
			Foreach(ord, ords_per_dst[next_nid]) {
				score += T_max2 - twice(T.cur - ord.ord_time);
			}
			ords_per_dst[next_nid].clear();
			cmds.push_back(next_nid);
		}
		cur_nid = next_nid;
	}
	return score;
}
 
 
void put_orders(vector<order_t> &ords, const vector<vector<order_t>> &ords_per_dst) {
	ords.clear();
	Loop(i, ords_per_dst.size()) {
		Foreach(ord, ords_per_dst[i]) {
			ords.push_back(ord);
		}
	}
}
 
ll evalfunc(const graph_t &G, int cur_nid, int next_nid, const vector<vector<order_t>> &ords_per_dst, const orderlist_t &ordlst, localtime_t T) {
	const ll T_max2 = twice(ordlst.T_max);
	ll eval = 0;
	T.cur += G.table[cur_nid][next_nid];
	T.rem -= G.table[cur_nid][next_nid];
	Foreach(ord, ords_per_dst[next_nid]) {
		eval += T_max2 - twice(T.cur - ord.ord_time);
	}
	return eval;
}
 
void calc_mid_evalfunc(const graph_t &G, const orderlist_t &ordlst, int cur_nid, int snd_nid, vector<vector<order_t>> &ords_per_dst, ll &score, vector<int> &cmds, localtime_t &T) {
	while (T.rem > 0) {
		int best_next_nid = -1;
		if (snd_nid != -1) {
			best_next_nid = snd_nid;
			snd_nid = -1;
		}
		else {
			map<int, vi> mp;
			Loop(next_cand_nid, G.n) {
				if (ords_per_dst[next_cand_nid].size()) {
					mp[G.table[cur_nid][next_cand_nid]].push_back(next_cand_nid);
				}
			}
			auto itr = mp.begin();
			if (itr != mp.end() && itr->fst <= T.rem) {
				if (itr->snd.size() >= 2) {
					ll best_eval = LLONG_MIN;
					Foreach(next_cand_nid, itr->snd) {
						if (G.table[cur_nid][next_cand_nid] + G.table[next_cand_nid][0] <= T.rem) {
							ll eval = evalfunc(G, cur_nid, next_cand_nid, ords_per_dst, ordlst, T);
							if (eval > best_eval) {
								best_next_nid = next_cand_nid;
								best_eval = eval;
							}
						}
					}
				}
				else {
					best_next_nid = itr->snd[0];
				}
			}
		}
		if (best_next_nid == -1) break;
		score += move_next(G, ordlst, cur_nid, best_next_nid, ords_per_dst, cmds, T);
	}
	if (cmds.size()) {
		score += move_next(G, ordlst, cur_nid, 0, ords_per_dst, cmds, T);
	}
}
 
void another_mid_walk(const graph_t &G, const orderlist_t &ordlst, vector<vector<order_t>> &ords_per_dst, ll &score, vector<int> &cmds, localtime_t &T) {
	const ll T_max2 = twice(ordlst.T_max);
	vector<int> cmds_buf = cmds;
	cmds.clear();
	int cur_nid = 0;
	Loop(i, cmds_buf.size()) {
		int dst_nid;
		if (cmds_buf[i] == 0) dst_nid = cmds_buf[i];
		else if (i >= int(cmds_buf.size()) - 2) dst_nid = cmds_buf[i];
		else if (cmds_buf[i + 1] == 0) dst_nid = cmds_buf[i];
		else if (ords_per_dst[cmds_buf[i]].size() == 0) continue;
		else {
			if (G.table[cur_nid][cmds_buf[i]] + G.table[cmds_buf[i]][cmds_buf[i + 1]] + G.table[cmds_buf[i + 1]][cmds_buf[i + 2]]
			< G.table[cur_nid][cmds_buf[i + 1]] + G.table[cmds_buf[i + 1]][cmds_buf[i]] + G.table[cmds_buf[i]][cmds_buf[i + 2]]) continue;
			vvi nids = {{ cmds_buf[i], cmds_buf[i + 1], cmds_buf[i + 2] },
					{ cmds_buf[i + 1], cmds_buf[i], cmds_buf[i + 2] }};
			vll local_score(2, 0);
			vector<localtime_t> local_T(2, T);
			Loop(j, 2) {
				int cur_local_nid = cur_nid;
				Loop(k, 3) {
					int dst_local_nid = nids[j][k];
					while (cur_local_nid != dst_local_nid) {
						int next_local_nid = G.route[cur_local_nid][dst_local_nid];
						local_T[j].cur += G.table[cur_local_nid][next_local_nid];
						local_T[j].rem -= G.table[cur_local_nid][next_local_nid];
						Foreach(ord, ords_per_dst[next_local_nid]) {
							local_score[j] += T_max2 - twice(local_T[j].cur - ord.ord_time);
						}
						cur_local_nid = next_local_nid;
					}
				}
			}
			if ((local_score[0] < local_score[1] && local_T[0].rem <= local_T[1].rem)
			&& (local_score[0] <= local_score[1] && local_T[0].rem < local_T[1].rem)) {
				dst_nid = cmds_buf[i + 1];
				swap(cmds_buf[i], cmds_buf[i + 1]);
			}
			else {
				dst_nid = cmds_buf[i];
			}
		}
		score += move_next(G, ordlst, cur_nid, dst_nid, ords_per_dst, cmds, T);
	}
}
 
// Local step: send orders as possible in time T (begin from 0 and end at 0), return score
ll solve_mid_localstep(const graph_t &G, const orderlist_t &ordlst, vector<order_t> &ords, vector<int> &cmds, localtime_t &T) {
	const int TRIAL_CNT = 20;
	vector<vector<order_t>> ords_per_dst(G.n);
	Foreach(ord, ords) {
		ords_per_dst[ord.dst_nid].push_back(ord);
	}
	vector<ll> near_scores(TRIAL_CNT, 0);
	vector<vector<vector<order_t>>> near_ords_per_dst(TRIAL_CNT, ords_per_dst);
	vector<vector<int>> near_cmds(TRIAL_CNT);
	vector<localtime_t> near_T(TRIAL_CNT, T);
	int cnt = 0;
	Foreach(dst_nid, G.dst_seq) {
		if (cnt == TRIAL_CNT) break;
		if (ords_per_dst[dst_nid].size()) {
			calc_mid_evalfunc(G, ordlst, 0, dst_nid, near_ords_per_dst[cnt], near_scores[cnt], near_cmds[cnt], near_T[cnt]);
			cnt++;
		}
	}
	if (cnt == 0) {
		return 0;
	}
	else {
		ll best_score = LLONG_MIN;
		int best_id = -1;
		Loop(i, cnt) {
			if (best_score < near_scores[i]) {
				best_score = near_scores[i];
				best_id = i;
			}
		}
		ll another_score = 0;
		vector<int> another_cmds = near_cmds[best_id];
		localtime_t another_T = T;
		another_mid_walk(G, ordlst, ords_per_dst, another_score, another_cmds, another_T);
		if (another_score > best_score) {
			cmds = another_cmds;
			T = another_T;
			put_orders(ords, ords_per_dst);
			return another_score;
		}
		else {
			cmds = near_cmds[best_id];
			T = near_T[best_id];
			put_orders(ords, near_ords_per_dst[best_id]);
			return best_score;
		}
	}
}
 
void calc_last_evalfunc(const graph_t &G, const orderlist_t &ordlst, int cur_nid, int snd_nid, vector<vector<order_t>> &ords_per_dst, ll &score, vector<int> &cmds, localtime_t &T) {
	while (T.rem > 0) {
		int best_next_nid = -1;
		if (snd_nid != -1) {
			best_next_nid = snd_nid;
			snd_nid = -1;
		}
		else {
			map<int, vi> mp;
			Loop(next_cand_nid, G.n) {
				if (ords_per_dst[next_cand_nid].size()) {
					mp[G.table[cur_nid][next_cand_nid]].push_back(next_cand_nid);
				}
			}
			auto itr = mp.begin();
			if (itr != mp.end() && itr->fst <= T.rem) {
				if (itr->snd.size() >= 2) {
					ll best_eval = LLONG_MIN;
					Foreach(next_cand_nid, itr->snd) {
						if (G.table[cur_nid][next_cand_nid] <= T.rem) {
							ll eval = evalfunc(G, cur_nid, next_cand_nid, ords_per_dst, ordlst, T);
							if (eval > best_eval) {
								best_next_nid = next_cand_nid;
								best_eval = eval;
							}
						}
					}
				}
				else {
					best_next_nid = itr->snd[0];
				}
			}
		}
		if (best_next_nid == -1) break;
		score += move_next(G, ordlst, cur_nid, best_next_nid, ords_per_dst, cmds, T);
	}
	if (T.rem > 0) {
		cmds.push_back(-T.rem);
		T.cur += T.rem;
		T.rem -= T.rem;
	}
}
 
void another_last_walk(const graph_t &G, const orderlist_t &ordlst, vector<vector<order_t>> &ords_per_dst, ll &score, vector<int> &cmds, localtime_t &T) {
	const ll T_max2 = twice(ordlst.T_max);
	vector<int> cmds_buf = cmds;
	cmds.clear();
	int cur_nid = 0;
	Loop(i, cmds_buf.size()) {
		int dst_nid;
		if (cmds_buf[i] < 0) break;
		else if (cmds_buf[i] == 0) dst_nid = cmds_buf[i];
		else if (i >= int(cmds_buf.size()) - 2) dst_nid = cmds_buf[i];
		else if (cmds_buf[i + 1] == 0) dst_nid = cmds_buf[i];
		else if (cmds_buf[i + 2] < 0) dst_nid = cmds_buf[i];
		else if (ords_per_dst[cmds_buf[i]].size() == 0) continue;
		else {
			if (G.table[cur_nid][cmds_buf[i]] + G.table[cmds_buf[i]][cmds_buf[i + 1]] + G.table[cmds_buf[i + 1]][cmds_buf[i + 2]]
			< G.table[cur_nid][cmds_buf[i + 1]] + G.table[cmds_buf[i + 1]][cmds_buf[i]] + G.table[cmds_buf[i]][cmds_buf[i + 2]]) continue;
			vvi nids = {{ cmds_buf[i], cmds_buf[i + 1], cmds_buf[i + 2] },
					{ cmds_buf[i + 1], cmds_buf[i], cmds_buf[i + 2] }};
			vll local_score(2, 0);
			vector<localtime_t> local_T(2, T);
			Loop(j, 2) {
				int cur_local_nid = cur_nid;
				Loop(k, 3) {
					int dst_local_nid = nids[j][k];
					while (cur_local_nid != dst_local_nid) {
						int next_local_nid = G.route[cur_local_nid][dst_local_nid];
						local_T[j].cur += G.table[cur_local_nid][next_local_nid];
						local_T[j].rem -= G.table[cur_local_nid][next_local_nid];
						Foreach(ord, ords_per_dst[next_local_nid]) {
							local_score[j] += T_max2 - twice(local_T[j].cur - ord.ord_time);
						}
						cur_local_nid = next_local_nid;
					}
				}
			}
			if ((local_score[0] < local_score[1] && local_T[0].rem <= local_T[1].rem)
			&& (local_score[0] <= local_score[1] && local_T[0].rem < local_T[1].rem)) {
				dst_nid = cmds_buf[i + 1];
				swap(cmds_buf[i], cmds_buf[i + 1]);
			}
			else {
				dst_nid = cmds_buf[i];
			}
		}
		score += move_next(G, ordlst, cur_nid, dst_nid, ords_per_dst, cmds, T);
	}
	calc_last_evalfunc(G, ordlst, cur_nid, -1, ords_per_dst, score, cmds, T);
}
 
// Local step: send orders as possible in time T (begin from 0 and end at 0), return score
ll solve_last_localstep(const graph_t &G, const orderlist_t &ordlst, vector<order_t> &ords, vector<int> &cmds, localtime_t &T) {
	const int TRIAL_CNT = 20;
	vector<vector<order_t>> ords_per_dst(G.n);
	Foreach(ord, ords) {
		ords_per_dst[ord.dst_nid].push_back(ord);
	}
	vector<ll> near_scores(TRIAL_CNT, 0);
	vector<vector<vector<order_t>>> near_ords_per_dst(TRIAL_CNT, ords_per_dst);
	vector<vector<int>> near_cmds(TRIAL_CNT);
	vector<localtime_t> near_T(TRIAL_CNT, T);
	int cnt = 0;
	Foreach(dst_nid, G.dst_seq) {
		if (cnt == TRIAL_CNT) break;
		if (ords_per_dst[dst_nid].size()) {
			calc_last_evalfunc(G, ordlst, 0, dst_nid, near_ords_per_dst[cnt], near_scores[cnt], near_cmds[cnt], near_T[cnt]);
			cnt++;
		}
	}
	if (cnt == 0) {
		cmds = { -T.rem };
		T.cur += T.rem;
		T.rem -= T.rem;
		return 0;
	}
	else {
		ll best_score = LLONG_MIN;
		int best_id = -1;
		Loop(i, cnt) {
			if (best_score < near_scores[i]) {
				best_score = near_scores[i];
				best_id = i;
			}
		}
		ll another_score = 0;
		vector<int> another_cmds = near_cmds[best_id];
		localtime_t another_T = T;
		another_last_walk(G, ordlst, ords_per_dst, another_score, another_cmds, another_T);
		if (another_score > best_score) {
			cmds = another_cmds;
			T = another_T;
			put_orders(ords, ords_per_dst);
			return another_score;
		}
		else {
			cmds = near_cmds[best_id];
			T = near_T[best_id];
			put_orders(ords, near_ords_per_dst[best_id]);
			return best_score;
		}
	}
}

Measured memory_bytes: 13624