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 <utility>
#include <queue>
#include <algorithm>
#include <queue>
#include <unordered_map>

typedef int Weight;
struct Edge {
	int src, dst;
	Weight weight;
	Edge() {
		this->src = -1;
		this->dst = -1;
		this->weight = -1;
		//	std::cout << "aaa" << std::endl;
	}
	;
	Edge(const Edge &obj) {
		//std::cout << "bbb" << std::endl;
		src = obj.src;
		dst = obj.dst;
		weight = obj.weight;
	}
	Edge(int src, int dst, Weight weight) :
			src(src), dst(dst), weight(weight) {
	}
};

bool operator <(const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
			e.src != f.src ? e.src < f.src : e.dst < f.dst;
}

typedef std::unordered_map<int, Edge> Edges;
typedef std::vector<Edges> Graph;

typedef std::vector<Weight> Array;
typedef std::vector<Array> Matrix;
#define INF 10000

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()

void shortestPath(const Graph &g, int s, std::vector<Weight> &dist,
		std::vector<int> &prev) {
	int n = g.size();
	dist.assign(n, INF);
	dist[s] = 0;
	prev.assign(n, -1);
	std::priority_queue<Edge> Q; // "e < f" <=> "e.weight > f.weight"
	for (Q.push(Edge(-2, s, 0)); !Q.empty();) {
		Edge e = Q.top();
		Q.pop();
		if (prev[e.dst] != -1)
			continue;
		prev[e.dst] = e.src;
		//FOR(f, g[e. dst])
		for (__typeof((g[e.dst]).begin()) i = (g[e.dst]).begin();
				i != (g[e.dst]).end(); ++i) {
			Edge f = i->second;
			if (dist[f.dst] > e.weight + f.weight) {
				dist[f.dst] = e.weight + f.weight;
				Q.push(Edge(f.src, f.dst, e.weight + f.weight));
			}
		}
	}
}

std::vector<int> buildPath(const std::vector<int> &prev, int t) {
	std::vector<int> path;
	for (int u = t; u >= 0; u = prev[u])
		path.push_back(u);
	reverse(path.begin(), path.end());
	return path;
}

int main() {
	// recieve |V| and |E|
	int V, E;
	std::cin >> V >> E;
	std::vector<std::vector<std::pair<int, int> > > G(V);

	Graph gra = Graph(V);
	Edges edges = Edges();
	for (int i = 0; i < E; i++) {
		// recieve edges
		int u, v, d;
		std::cin >> u >> v >> d;
		u--;
		v--;
		//G[u].push_back({v,d});
		G[u].push_back(std::pair<int, int>(v, d));
		G[v].push_back(std::pair<int, int>(v, d));
		gra[u][v] = Edge(u, v, d);
		gra[v][u] = Edge(v, u, d);
	}

	//gra.push_back(edges);
	std::vector<Weight> dist = std::vector<Weight>();
	std::vector<int> prev = std::vector<int>();

//	std::cout << "start" << std::endl;
	//for(int i = 0 ; i < dist.size();i++){
	//		std::cout << "oh"<< dist[i];
	//}

	int Tmax;
	std::cin >> Tmax;
	std::queue<int> order;

	shortestPath(gra, 0, dist, prev);
	//for(int i =0;i<prev.size();i++){
	//	std::cout << prev[i]+1 << std::endl;
	//}
	// recieve info
	for (int t = 0; t < Tmax;) {
		int Nnew;
		std::cin >> Nnew;
		for (int j = 0; j < Nnew; j++) {
			int new_id, dst;
			std::cin >> new_id >> dst;
			//std::cout << new_id << " "<<dst<< std::endl;
			order.push(dst);
		}
		if (order.empty()) {
			std::cout <<  -1 << std::endl;
			t++;
			continue;
		}
		int next_order = order.front();

		//std::cout << next_order << "  " << std::endl; // 先頭要素を参照する
		order.pop(); // 先頭要素を削除
		std::vector<int> path = buildPath(prev, next_order-1);

		int pre_i = path[0];
//		if(next_order == 352){
//			for(int i =0;i<path.size();i++){
//				std::cout<<path[i] << " ";
//			}
//			std::cout << std::endl;
//		}
		for (int i = 0; i < path.size(); i++) {
			if (i != 0) {
				int w = gra[pre_i][path[i]].weight;
				//std::cout << "("<< gra[pre_i][path[i]].weight << ")";
				//std::cout << path[i] +1 ;
				for (int j = 0; j < w; j++) {
					std::cout <<  path[i]  +1 << std::endl;
					t++;
					if (t >= Tmax) {
						goto end;
					}
				}
			}
//				std::cout << path[i] << " ";
			pre_i = path[i];
		}
		//std::cout << std::endl;
		std::reverse(path.begin(), path.end());
		pre_i = path[0];
		for (int i = 0; i < path.size(); i++) {
			if (i != 0) {
				//	std::cout << "("<< gra[pre_i][path[i]].weight << ")";
//					std::cout << path[i] << " ";
				int w = gra[pre_i][path[i]].weight;
				for (int j = 0; j < w; j++) {
					std::cout << path[i] +1 << std::endl;
					t++;
					if (t >= Tmax) {
						goto end;
					}
				}
			}
			pre_i = path[i];
		}
//		std::cout << std::endl;
	}
	end:
//	std::cout << "end" << std::endl;

// insert your code here to get more meaningful output
// all stay
// for(int i = 0; i < Tmax; i++) std::cout << -1 << std::endl;

	return 0;
}