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 <algorithm>
#include <queue>
using namespace std;

struct road {
  int to, cost;
};

struct M {
  int cost, from;
  vector<int> route;
};

bool operator>(const M& m1, const M& m2) {
  if (m1.cost == m2.cost) {
    return m1.from < m2.from;
  } else {
    return m1.cost < m2.cost;
  }
}

int main() {
  int v, e; cin >> v >> e;
  vector<road> r[v];
  
  for(int i=0; i<e; i++) {
    int a, b, c;
    cin >> a >> b >> c; a--; b--;
    r[a].push_back({b,c});
    r[b].push_back({a,c});
  }
  
  int fs[v][v]; fill(fs[0], fs[v], 1e9);
  vector<int> fs_route[v][v];
  for(int i=0; i<v; i++) {
    priority_queue<M, vector<M>, greater<M>> q;
    fs[i][i] = 0;
    
    q.push({0,i});
    
    while(!q.empty()) {
      M p = q.top(); q.pop();
      int cost = p.cost, from = p.from;
      if (fs[i][from] < cost) continue;
      for(road x:r[from]) {
        if (fs[i][x.to] > fs[i][from] + x.cost) {
          fs[i][x.to] = fs[i][from] + x.cost;
          
          vector<int> x_route = p.route; x_route.push_back(x.to);
          fs_route[i][x.to] = x_route;
            
          q.push({fs[i][x.to], x.to, x_route});
        }
      }
    }
  }
  
  int Tmax; cin >> Tmax;
  int tm[Tmax]; fill(tm, tm+Tmax, -1);
  int n;
  
  for(int i=0; i<Tmax; i++) {
    int _; cin >> n;
    if (n) {cin >> _ >> tm[i]; tm[i]--;}
  }
  
  /*
  
  for(int time = 0; time < Tmax; time ++) {
    int nww; cin >> nww; if (nww) {int new_one; cin >> new_one;}
    int npu; cin >> npu; for(int i=0; i<npu; i++)  ccccccc;
    
  }
  
  */
  
  int tasks_queue[v], tasks_ongoing[v];
  fill(tasks_queue, tasks_queue+v, 0); fill(tasks_ongoing, tasks_ongoing+v, 0); 
  queue<int> going_place;
  
  int nw = 0, nx = 0, remain = 0;
  //cout << "Hi" << endl;
  
  for(int time=0; time < Tmax; time++) {
    //cout << "&" << time << ": " << remain << ", " << nw << ", " << nx << ", " << finiced_task << ", " << happened_task << " ";
    tasks_queue[tm[time]]++;
    if (nw == 0 && remain == 0) {
      //cout << "z";
      for(int i=0; i<v; i++) {
        tasks_ongoing[i] += tasks_queue[i]; tasks_queue[i] = 0;
      }
      int mn = 1e9, id = -1;
      for(int i=0; i<v; i++) {
        if (tasks_ongoing[i] > 0 && mn > fs[0][i] / tasks_ongoing[i]) {
          mn = fs[0][i] / tasks_ongoing[i]; id = i;
        }
      }
      if (id == -1) {puts("-1"); continue;}
      //cout << "(";
      for(int x:fs_route[0][id]) {
        going_place.push(x); //cout << x << " "; if (!x) break;
      } //cout << ")\n";
      nw = 0; nx = going_place.front(); remain = fs[nw][nx];
      tasks_ongoing[id] = 0;
    }
    if (remain > 1) {
      //cout << "o";
      cout << nx+1 << endl; remain--; //cout << "^" << going_place.size() << " ";
    }
    else if (remain == 1) {
      //cout << "j";
      cout << nx+1 << endl; remain--;
      if (going_place.size() > 1) {
        nw = nx; going_place.pop(); nx = going_place.front();
        remain = fs[nw][nx]; //cout << nw << " " << nx << endl;
      }
      else if (nx != 0){
        nw = going_place.front(); going_place.pop();
        
        int mn = 1e9, id = 0;
        for(int i=0; i<v; i++) {
          if (tasks_ongoing[i] > 0 && mn > fs[nw][i] / tasks_ongoing[i]) {
            mn = fs[nw][i] / tasks_ongoing[i]; id = i;
          }
        }
        
        for(int x:fs_route[nw][id]) {going_place.push(x); if (!x) break;}
        nx = going_place.front();
        remain = fs[nw][nx];
        tasks_ongoing[id] = 0;
      } else {
        going_place.pop(); nw = 0;
      } 
    }
  }
}