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 <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;
template<class T> struct edge{
	int to;
	T wt;
	edge(int to,const T& wt):to(to),wt(wt){}
};
template<class T> using weighted_graph=vector<vector<edge<T>>>;

const int INF=1<<29;

int main(){
	int n,m; scanf("%d%d",&n,&m);
	weighted_graph<int> G(n);
	rep(i,m){
		int u,v,d; scanf("%d%d%d",&u,&v,&d); u--; v--;
		G[u].emplace_back(v,d);
		G[v].emplace_back(u,d);
	}
	int Tmax; scanf("%d",&Tmax);

	// Warshall-Floyd
	vector<vector<int>> d(n,vector<int>(n,INF));
	rep(u,n) d[u][u]=0;
	rep(u,n) for(auto e:G[u]) {
		int v=e.to;
		d[u][v]=min(d[u][v],e.wt);
	}
	rep(w,n) rep(u,n) rep(v,n) d[u][v]=min(d[u][v],d[u][w]+d[w][v]);

	list<pair<int,int>> Wait,Now;
	int phase=0;
	int cur=0,next,edge_pos,goal;
	bool on_edge=false;
	rep(t,Tmax){
		int n_new; scanf("%d",&n_new);
		if(n_new>0){
			int id,dst; scanf("%d%d",&id,&dst); id--; dst--;
			Wait.emplace_back(id,dst);
		}

		int res=-1;

		if(phase%2==0 && cur==0){ // at the shop
			Now.insert(Now.end(),Wait.begin(),Wait.end());
			Wait.clear();
			if(!Now.empty()){
				goal=Now.front().second;
				phase++;
			}
		}
		else if(phase%2==0){ // at customer
			for(auto it=Now.begin();it!=Now.end();++it) if(it->second==goal) {
					it=Now.erase(it);
					--it;
			}
			goal=0;
			for(auto p:Now){
				if(goal==0 || d[cur][p.second]<d[cur][goal]) goal=p.second;
			}
			phase++;
		}

		if(phase%2==1){ // moving
			if(!on_edge){
				next=-1;
				for(auto e:G[cur]){
					if(next==-1 || d[cur][goal]==e.wt+d[e.to][goal]) next=e.to;
				}
				edge_pos=1;
				on_edge=true;
			}
			else{ // on_edge
				edge_pos++;
			}
			res=next;

			if(on_edge && edge_pos==d[cur][next]){
				on_edge=false;
				if(next==goal){
					phase++;
				}
				cur=next;
			}
		}

		printf("%d\n",res==-1?-1:res+1);
	}

	return 0;
}