Problem: Requirements

* All inputs are of non-negative integer value.
* T_{\text{max}} = 10000
* 200 \leq |V| \leq 400
* 1.5 |V| \leq |E| \leq 2 |V|
* 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
* 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
* The given graph has no self-loops / multiple edges and is guaranteed to be connected.
* 0 \leq N_{\text{new}} \leq 1
* 1 \leq \mathrm{new\\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}}). Note: If all orders are generated by the order generation rule as explained above, the total number of orders is at most T_{\text{last}}+1. Therefore, the possible range of \mathrm{new\\_id}_{i} should be from 1 to T_{\text{last}}+1.
* 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
* The order IDs \mathrm{new\\_{id}}_i are unique.

Input Format

Input is provided in the following form:


|V| |E|
u_{1} v_{1} d_{u_{1}, v_{1}}
u_{2} v_{2} d_{u_{2}, v_{2}}
:
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
T_{\text{max}}
\mathrm{info}_{0}
\mathrm{info}_{1}
:
\mathrm{info}_{T_{\text{max}}-1}


* In the first line |V| denotes the number of vertices, while |E| denotes the number of edges.
* The following |E| lines denote the edges of the graph. In particular, in the ith line u_{i} and v_{i} denote the edge connecting u_{i} and v_{i} and d_{u_{i}, v_{i}} the corresponding distance.
* The following line denotes the number of steps T_{\text{max}}.



In the following line, \mathrm{info}_t is information about the order from the customer that occurs at time t. \mathrm{info}_t is given in the form:


N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}


* N_{\text{new}} represents the number of new orders which appear at time t.
* The next N_{\text{new}} lines give the newly generated order information. The i-th order information indicates that the order ID \mathrm{new\\_{id}}_i of the new order, while \mathrm{dst}_i denotes the vertex to which the customer wishes the order to be delivered.
* Note: If N_{\text{new}}=0, there are no new lines.

Output Format

The Output expects T_{\text{max}} integers in the format specified below.


\mathrm{command}_{0}
\mathrm{command}_{1}
:
\mathrm{command}_{T_{\text{max}}-1}


In particular, \mathrm{command}_{i} shall specify the movement of the delivery car by using one of the following two options:

1) `stay`, if the car shall not move:


-1


2) `move w`, if the car shall be moved one step towards the neighboring vertex w


w


Note that in case of 2) w has to satisfy the following conditions:

* w \in V
* If the car is at vertex u: \left\\{ u, w \right\\} \in E .
* If the car is on the edge \left\\{ u, v \right\\}, w must either satisfy u = w or v = w.



* * *

Examples

Input




Output




Input

5 7
1 2 5
5 3 4
2 4 8
1 5 1
2 3 3
4 5 3
4 3 9
4
1
1 2
1
2 5
1
3 4
0


Output

2
-1
1
5

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cassert>
using namespace std;

// v----- Input -----v
struct Edge {
	int to;
	int dist;
};

int n, m;
vector< vector< Edge > > edge;
int T_MAX;
vector< int > dst;
// ^----- Input -----^

// v----- Shortest Path Management -----v
int len_uv[402][402];
int dist_st[402][402];
int next_st[402][402];

int getLen(int u, int v) { return len_uv[u][v]; }
int getDist(int s, int t) { return dist_st[s][t]; }
int getNext(int s, int t) { return next_st[s][t]; }

void findShortestPaths() {
	struct State {
		int v;
		int dist;
		bool operator > (const State& o) const { return dist > o.dist; }
	};
	
	memset(len_uv, -1, sizeof(len_uv));
	memset(dist_st, -1, sizeof(dist_st));
	memset(next_st, -1, sizeof(next_st));
	
	for (int v=0; v<n; ++v) {
		for (const Edge& e : edge[v]) {
			len_uv[v][e.to] = e.dist;
		}
	}
	
	for (int s=0; s<n; ++s) {
		priority_queue< State, vector< State >, greater< State > > que;
		que.push(State{s, 0});
		dist_st[s][s] = 0;
		
		while (!que.empty()) {
			State sta = que.top(); que.pop();
			if (dist_st[s][sta.v] < sta.dist) continue;
			for (const Edge& e : edge[sta.v]) {
				if (dist_st[s][e.to] == -1 || dist_st[s][e.to] > sta.dist + e.dist) {
					dist_st[s][e.to] = sta.dist + e.dist;
					next_st[e.to][s] = sta.v;
					que.push(State{e.to, dist_st[s][e.to]});
				}
			}
		}
	}
}
// ^----- Shortest Path Management -----^

// v----------------------------------- Solver -----------------------------------v

void COMMAND_STAY() { cout << -1 << endl; }
void COMMAND_MOVE(int w) { cout << w+1 << endl; }

void putOrder(vector< vector< int > >& order_que, int t1, int t2) {
	for (int t=t1; t<=t2; ++t) {
		if (dst[t] >= 0) {
			order_que[dst[t]].push_back(t);
		}
	}
}

void solve() {
	int cur_v = 0, tar_v = -1, len = 0, prev_put_t = 0;
	vector< vector< int > > order_que(n, vector< int >());
	
	for (int t=0; t<T_MAX; ++t) {
		if (cur_v == 0 && len == 0) { // put
			putOrder(order_que, prev_put_t, t);
			prev_put_t = t+1;
		}
		
		// decide target
		if (tar_v == -1) {
			tar_v = 0;
			int min_value = 1L << 30;
			for (int v=1; v<n; ++v) {
				int value = getDist(cur_v, v);
				if (!order_que[v].empty() && min_value > value) {
					tar_v = v;
					min_value = value;
				}
			}
		}
		
		if (cur_v == tar_v) {
			COMMAND_STAY();
			tar_v = -1;
		}
		else {
			int nxt_v = getNext(cur_v, tar_v);
			if (len == 0) len = getLen(cur_v, nxt_v);
			COMMAND_MOVE(nxt_v);
			--len;
			if (len == 0) cur_v = nxt_v;
			if (cur_v == tar_v) {
				order_que[tar_v].clear();
				tar_v = -1;
			}
		}
	}
}

// ^----------------------------------- Solver -----------------------------------^

int main() {
	cin >> n >> m;
	edge.assign(n, vector< Edge >());
	for (int i=0; i<m; ++i) {
		int u, v, d;
		cin >> u >> v >> d;
		--u; --v;
		edge[u].push_back(Edge{v, d});
		edge[v].push_back(Edge{u, d});
	}
	findShortestPaths();
	
	cin >> T_MAX;
	dst.assign(T_MAX, -1);
	for (int i=0; i<T_MAX; ++i) {
		int N_new;
		cin >> N_new;
		for (int j=0; j<N_new; ++j) {
			int id, v;
			cin >> id >> v;
			--v;
			dst[i] = v;
		}
	}
	
	solve();
}