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 <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <string>
#include <limits.h>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <random>
#include <fstream>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b)
{
  ll r;
  while ((r = a % b))
  {
    a = b;
    b = r;
  }
  return b;
}

struct edge
{
  int u, v, d;
  bool operator<(const edge &right) const
  {
    if (u == right.u)
    {
      return d < right.d;
    }
    else
    {
      return u < right.u;
    }
  }
};

struct order
{
  int t, id, dst;
};

struct road
{
  int v,d;

};

int main()
{

  int vSize, eSize;
  cin >> vSize >> eSize;
  vector<edge> e(eSize * 2);
  rep(i, eSize) { cin >> e[i].u >> e[i].v >> e[i].d; }
  int Tmax;
  cin >> Tmax;
  vector<order> ord;
  rep(i, Tmax)
  {
    int n;
    cin >> n;
    rep(i, n)
    {
      order o;
      o.t = i;
      cin >> o.id >> o.dst;
      ord.push_back(o);
    }
  }

  rep(i, eSize)
  {
    e[i + eSize].u = e[i].v;
    e[i + eSize].v = e[i].u;
    e[i + eSize].d = e[i].d;
  }

  sort(e.begin(), e.end());

  /*
  ofstream outputfile("output.txt");

  rep(i, Tmax)
  {
    outputfile << "-1" << endl;
  }

  outputfile.close();
  */

  /*
  // 辺の情報を表示
  cout << "u"
       << " "
       << "v"
       << " "
       << "d" << endl;
  rep(i, eSize * 2)
  {
    cout << e[i].u << " " << e[i].v << " " << e[i].d << endl;
  }
  */

  vector<vector<road> > v(vSize + 1);

  rep(i, eSize * 2)
  {
    road r={e[i].v,e[i].d};
    v[e[i].u].push_back(r);
    //v[e[i].v].push_back(e[i].u);
  }

  /*
  for (int i = 1; i <= vSize; i++)
  {
    cout << i << ":";
    for (int j = 0; j < v[i].size(); j++)
    {
      cout << "{" << v[i][j].v << ", " << v[i][j].d << "} ";
    }
    cout << endl;
  }
  */

  /*
  // 1から一番近いところを往復する

  int dMin = e[0].d;
  int dMinV = e[0].v;

  rep(i, eSize)
  {
    if (e[i].u == 1)
    {
      if (e[i].d < dMin)
      {
        dMin = e[i].d;
        dMinV = e[i].v;
      }
    }
    else
    {
      break;
    }
  }

  // 0が配達、1が集荷
  int state = 0;
  rep(t, Tmax)
  {
    if (t / dMin % 2 == 0)
    {
      state = 0;
    }
    else
    {
      state = 1;
    }
    if (state == 0)
    {
      cout << dMinV << endl;
    }
    else
    {
      cout << 1 << endl;
    }
  }
  */

  // 1から近いとこかつ行ってないところに行き、行き詰まったらその道を戻る、を繰り返す
  // まずルートを決定する
  vector<int> visited;
  vector<int> route;
  vector<int> routeT;
  visited.push_back(1);
  int current = 1;
  while (1)
  {
    int flag = 0;
    for (int i = 0; i < v[current].size(); i++)
    {
      if (!binary_search(visited.begin(), visited.end(), v[current][i].v))
      {
        routeT.push_back(v[current][i].d);
        current = v[current][i].v;
        auto it = visited.insert(lower_bound(visited.begin(), visited.end(), current), current);
        route.push_back(current);
        flag = 1;
        break;
      }
    }
    if (flag == 0)
    {
      break;
    }
  }

  /*
  cout << "route:{";
  rep(i, route.size())
  {
    cout << route[i];
    if (i < route.size() - 1)
    {
      cout << ", ";
    }
  }
  cout << "}" << endl;

  cout << "routeT:{";
  rep(i, routeT.size())
  {
    cout << routeT[i];
    if (i < routeT.size() - 1)
    {
      cout << ", ";
    }
  }
  cout << "}" << endl;
  */

  //ルートを往復する
  int t=0;
  while (t<Tmax){
  //行き
    rep(i,routeT.size()){
      rep(j,routeT[i]){
        cout << route[i] << endl;
        t++; if(t==Tmax){return 0;}
      }
    } 

  //帰り
    for (int i=routeT.size()-2; i>=0; i--){
      rep(j,routeT[i+1]){
        cout << route[i] << endl;
        t++; if(t==Tmax){return 0;}
      }
    }
    rep(i, routeT[0]){
      cout << 1 << endl;
      t++; if(t==Tmax){return 0;}
    }
  }

  return 0;
}