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 PYTHON3):

Solution:
#頂点数と辺数を取得
vertex_number, edge_number = map(int, input().split())

#隣接行列を作成 (辺がないところは 0，便宜上，(n+1)×(n+1)行列をつくっている)

A = [[0 for i in range(vertex_number+1)] for j in range(vertex_number+1)] #内包表記にしないと，一個の変更で複数のリストが変更されてしまうので注意
for i in range(edge_number):
    j,k,d = map(int, input().split())
    A[j][k] = d
    A[k][j] = d
    

#T_max と info を取得
T_max = int(input())
info = []

for i in range(T_max):
    x = int(input())
    if x == 0:
        info.append([x])
    else:
        y,z = map(int, input().split())
        info.append([x,y,z])


#フロイド・ワーシャル法
D = [[0 for i in range(vertex_number+1)] for j in range(vertex_number+1)] #最短距離行列
Next = [[0 for i in range(vertex_number+1)] for j in range(vertex_number+1)] #最短経路行列
#最短距離行列の初期化
for i in range(vertex_number+1):
    for j in range(vertex_number+1):
        if (i != 0) and (j != 0): #iが0 または j が0のときは何もしない
            if i == j:             # i=j のときは 0
                D[i][j] = 0
            elif A[i][j] == 0:      #辺がないところは距離無限大
                D[i][j] = 100000
            else: D[i][j] = A[i][j] #辺があるところはその辺の長さ

#最短経路行列の初期化
for i in range(vertex_number+1):
    for j in range(vertex_number+1):
        if (i != 0) and (j != 0) and (i != j): 
            Next[i][j] = j
#最短距離行列の計算
for k in range(vertex_number+1):
    for i in range(vertex_number+1):
        for j in range(vertex_number+1):
            if (k != 0) and (i != 0) and (j != 0):
                if D[i][j] > D[i][k]+D[k][j]:
                    D[i][j] = D[i][k]+D[k][j]
                    Next[i][j] = Next[i][k]
                    
                    
                    
                    

def Shortest_path(i,j): #iからj への最短経路をリストとして出力
    SP = [i]
    x = Next[i][j]
    while x != j:
        SP.append(x)
        x = Next[x][j]
    SP.append(x)
    return SP

'''
def Request(a,b): #時刻 a< t<=b の間に発生したリクエスト　(注文個数と注文IDと頂点)のリストのリストを出力
    R = []
    if a == b: #a=b ならば [] を出力
        return R
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                R.append(info[i+a+1])
        return R
'''
def Request(a,b): #時刻 a< t<=b の間に発生したリクエストの頂点をかぶりをなくして出力
    R = []
    if a == b: #a=b ならば [] を出力
        return R
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                if info[i+a+1][2] not in R:
                    R.append(info[i+a+1][2])
        return R

#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

while t < T_max-1:
    Req = [] #おとづれたいactive vertex set
    if Request(t_start,t) == []: # いまもっているおとづれるべき頂点集合が空ならばリクエストが来るまで待つ
        while (info[t] == [0]) and (t != T_max - 1):
            t += 1
            Root.append(-1)
        if t != T_max - 1:
            Req.append(info[t][2])

    else:
        Req = Request(t_start,t)
        
    t_start = t
        
    if t != T_max - 1:
        
        t_path = 0       
        active_path = [1]
        real_path = []
        while Req != []:
            x = 0
            u = 0
            for i in range(len(Req)):
                if i == 0:
                    x = D[active_path[-1]][Req[0]]
                    u = Req[0]
                elif x > D[active_path[-1]][Req[i]]:
                    x = D[active_path[-1]][Req[i]]
                    u = Req[i]
            Req.remove(u)
            active_path.append(u)
            t_path += x
        t_path += D[active_path[-1]][1]
        active_path.append(1)
        t += t_path

        #active_pathからRootを作成
        for i in range(len(active_path)):
            if i == 0:
                real_path =real_path + Shortest_path(active_path[i],active_path[i+1])
            elif i != len(active_path)-1:
                real_path.pop(-1)
                real_path =real_path + Shortest_path(active_path[i],active_path[i+1])
        for j in range(len(real_path)):
            if j < len(real_path)-1:
                for k in range(A[real_path[j]][real_path[j+1]]):
                    Root.append(real_path[j+1])

#Root から最終出力を生成

for i in range(T_max):
    if i < len(Root):
        print(Root[i])
    else:
        print(-1)
'''
for i in range(T_max):
    print(-1)
'''