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"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 512;
vi P[N][N];
vi U[N][N];
vi comb(vi a,vi b) {
	vi c;
	for (auto it : a)
		c.pb(it);
	for (auto it : b)
		c.pb(it);
	return c;
}

db f(ll a,ll b) {
	return 1.0 * a / b;
}
vi O[N];
int main(void) {
	int n,m;
	cin>>n>>m;
	while (m --) {
		int u,v,w;
		cin>>u>>v>>w;
		for (int i = 0;i < w;++i) {
			P[u][v].pb(v);
			P[v][u].pb(u);
		}
	}
	auto Last = chrono::steady_clock::now().time_since_epoch().count();
	for (int k = 1;k <= n;++k)
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= n;++j)
				if (!P[i][k].empty() && !P[k][j].empty() && ((i != j && P[i][j].empty()) || P[i][j].size() > P[i][k].size() + P[k][j].size()))
					P[i][j] = comb(P[i][k],P[k][j]);
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= n;++j) {
			U[i][j] = P[i][j];
			sort(all(U[i][j]));
			U[i][j].resize(unique(all(U[i][j])) - U[i][j].begin());
		}
	cerr << "Pre-Process Time Taken: " << 1.0 * (chrono::steady_clock::now().time_since_epoch().count() - Last) / CLOCKS_PER_SEC << '\n';
	int Tmax;
	cin>>Tmax;
	for (int i = 0;i < Tmax;++i) {
		int Nnew;
		cin>>Nnew;
		while (Nnew --) {
			int ID,v;
			cin>>ID>>v;
			O[v].pb(i);
		}
	}
	int last = 0;
	int Vertex = 1;
	vi Answer;
	for (int i = 0;i < Tmax;) {
		if (Vertex == 1) {
			last = i;
		}
		pair < db , int > w = mp(0,1);
		for (int j = 1;j <= n;++j) {
			int cnt1 = lower_bound(all(O[j]),last + 1) - O[j].begin();
//			dbg(cnt1);
//			dbg(P[Vertex][j]);
			if (P[Vertex][j].empty())
				continue;
			smax(w,mp(f(cnt1,P[Vertex][j].size()),j));
			int cnt2 = lower_bound(all(O[j]),i + 1 + P[Vertex][1].size()) - O[j].begin();
//			dbg(cnt2);
			smax(w,mp(f(cnt2,P[Vertex][1].size() + P[1][j].size()),-j));
		}
		if (!w.fi) {
			Answer.pb(-1);
			++i;
			continue;
		}
		if (w.se < 0) {
			for (auto it : P[Vertex][1]) {
				Answer.pb(it);
				while (!O[it].empty() && O[it][0] <= last)
					O[it].erase(O[it].begin());
				++i;
			}
			Vertex = 1;
			last = i;
			w.se *= -1;
		}
		for (auto it : P[Vertex][w.se]) {
			Answer.pb(it);
			while (!O[it].empty() && O[it][0] <= last)
				O[it].erase(O[it].begin());
			++i;
		}
		Vertex = w.se;

	}
	if (Answer.size() > Tmax) {
		Answer.resize(Tmax);
	}
	for (auto it : Answer)
		cout << it << '\n';
    return 0;
}