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;

constexpr int INF = INT_MAX;

struct edge{
    int from, to, d;
    edge(){}
    edge(int from, int to, int d):from(from),to(to),d(d){}
};

struct Graph{
    int V;
    vector<vector<edge> > g;
    vector<vector<int> > dist;
    void init(int _V){
        V = _V;
        g.resize(V);
    }
    void add_edge(int u, int v, int d){
        g[u].push_back(edge(u,v,d));
        g[v].push_back(edge(v,u,d));
    }
    void wf(){
        dist.resize(V, vector<int>(V, INF/3));
        for(auto &v : g){
            for(auto &e : v){
                int u = e.from, v = e.to, d = e.d;
                dist[u][v] = d;
                dist[v][u] = d;
            }
        }
        for(int i=0;i<V;i++){
            dist[i][i] = 0;
        }
        for(int k=0;k<V;k++){
            for(int i=0;i<V;i++){
                for(int j=0;j<V;j++){
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
    }
    vector<edge> operator [](int i) {
        return g[i];
    }
};

vector<int> build_path(vector<int> ls, const Graph &graph){
    vector<int> nn = {0,0};
    for(auto x : ls){
        int dmin = INF, j = 1;
        for(int i=1;i<int(nn.size());i++){
            int tmp = graph.dist[nn[i-1]][x] + graph.dist[x][nn[i]] - graph.dist[nn[i-1]][nn[i]];
            if(tmp < dmin){
                j = i;
                dmin = tmp;
            }
        }
        nn.insert(nn.begin()+j,x);
    }
    nn.erase(nn.begin());
    return nn;
}

int main(void){
    int V, E, Tmax;
    // input
    cin >> V >> E;
    Graph graph;
    graph.init(V);
    for(int i=0;i<E;i++){
        int u, v, d;
        cin >> u >> v >> d;
        u--; v--;
        graph.add_edge(u,v,d);
    }
    cin >> Tmax;

    graph.wf();
    set<int> req;
    queue<int> reqque;
    vector<int> ls;
    vector<bool> remain(V);
    int now = 0, cnt = 0, nxt = 0;
    for(int t=0;t<Tmax;t++){
        int n;
        cin >> n;
        for(int i=0;i<n;i++){
            int id, dst;
            cin >> id >> dst;
            if(req.count(dst-1)==0){
                req.insert(dst-1);
                reqque.push(dst-1);
            }
        }
        if(now == 0){
            if(!reqque.empty()){
                vector<int> tmp;
                while(!reqque.empty()){
                    int dst = reqque.front();
                    if(!remain[dst]){
                        tmp.push_back(dst);
                        remain[dst] = true;
                    }
                    reqque.pop();
                }
                // ls.push_back(0);
                if(!tmp.empty()){
                    tmp = build_path(tmp, graph);
                    ls.insert(ls.end(), tmp.begin(), tmp.end());
                }
                remain[0] = true;
                req.clear();
            }
        }
        if(!ls.empty()){
            if(cnt == 0){
                int dst;
                while(!ls.empty()){
                    dst = ls.front();
                    if(remain[dst] && (now != dst)) break;
                    ls.erase(ls.begin());
                }
                for(auto &e : graph[now]){
                    if(now == e.to) continue;
                    if(graph.dist[now][e.to] + graph.dist[e.to][dst] == graph.dist[now][dst] && graph.dist[now][e.to] == e.d){
                        nxt = e.to;
                        cnt = e.d;
                        break;
                    }
                }
            }
            cout << nxt+1 << endl;
            now = -1;
            cnt--;
            if(cnt <= 0){
                now = nxt;
                remain[now] = false;
                while(!ls.empty() && now == ls.front()) ls.erase(ls.begin());
                // if(now == ls.front()) ls.erase(ls.begin());
            }
        }
        else{
            cout << -1 << endl;
        }
        // cout << now << " " << nxt << " " << cnt << " " << (ls.empty() ? -1 : ls.front()) << endl;
    }
    return 0;
}