Buggy python submission (verdict: Time Limit Exceeded):
import time
import random
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

'''
starttime = time.time()
'''

#頂点数と辺数を取得
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を作成する
D = [[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] = float("inf")
            else: D[i][j] = A[i][j] #辺があるところはその辺の長さ

D1,Prev = floyd_warshall(D,directed=False,return_predecessors=True)   #最短距離を求める(追記を参照)
for i in range(vertex_number+1):
    for j in range(vertex_number+1):
        if D1[i][j] != float("inf"):
            D[i][j] = int(D1[i][j])



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

'''
def Request(a,b): #時刻 a< t<=b の間に発生したリクエストの頂点をかぶりをなくして出力
    R = set()
    if a == b: #a=b ならば {} を出力
        return R
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                R.add(info[i+a+1][2])
        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

def Wt(a,b): #時刻 a< t<=b の間に発生したリクエストの時刻ti に対して，t-t_iを出力
    R = []
    WT = []
    if a == b: #a=b ならば [] を出力
        return WT
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                if info[i+a+1][2] not in R:
                    WT.append(b-(i+a+1))
                    R.append(info[i+a+1][2])
        return WT
'''  
def t_first(t): #時刻 t 以降にはじめて発生したリクエストの時刻を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    return time

def v_first(t): #時刻 t 以降にはじめて発生したリクエストの頂点を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    if time < T_max-1:
        return info[time][2]
    else:
        return 1


def T(*args): #頂点集合 args[0],...,args[k-1] を受け取って，それらを貪欲に通った時にかかる時間を計算
    if args == set():
        return 0
    else:
        Req_list = list(args)
        t_path = 0       
        active_path_last = 1
        while Req_list != []:
            x = 0
            u = 0
            for i in range(len(Req_list)):
                if i == 0:
                    x = D[active_path_last][Req_list[0]]
                    u = Req_list[0]
                elif x > D[active_path_last][Req_list[i]]:
                    x = D[active_path_last][Req_list[i]]
                    u = Req_list[i]
            Req_list.remove(u)
            active_path_last = u
            t_path += x
        t_path += D[active_path_last][1]
        active_path_last = 1 # 不要
        return t_path
'''
def f(x,Q,c): #リスト x,Q,cからxQx/2+xc を計算
    a = 0
    b = 0
    l = []

    for i in range(len(x)):
        d = 0
        for j in range(len(x)):
            d += Q[i][j]*x[j]
        l.append(d)
    for i in range(len(x)):
        b += x[i]*l[i]
        a += x[i]*c[i]
    return b/2+a

#2-opt
def opt2(L,s,t):#リストLと，index 1<= s <tをうけとって，v_s→→→v_t→→→ を v_s→v_t→v_{t-1}→→→v_{s+1}→v_{t+1}→→→ へ変更
    l =L.copy()
    start_list = l[:s+1]
    reverse_list = l[s+1:t+1]
    reverse_list = reverse_list[::-1]
    end_list = l[t+1:]
    return start_list+reverse_list+end_list


def score(L):#リストLをうけとって，そのスコアを計算
    x_L = [0 for i in range(k)]
    for i in range(k):
        if i == 0:
            x_L[i] = D[1][L[0]]
        else:
            x_L[i] = D[L[i-1]][L[i]]

    c_L = [0 for i in range(k)]
    for i in range(k):
        if i == 0:
            c_L[k-i-1] = W[Req.index(L[k-i-1])]
        else:
            c_L[k-i-1] = c_L[k-i] + W[Req.index(L[k-i-1])]
    return f(x_L,Q,c_L)


def dist(L):#リストLをうけとって，そのきょりを計算
    a = 0 
    for i in range(len(L)):
        if i != 0:
            a += D[L[i-1]][L[i]]
    if L[0] != 1:
        a += D[1][L[0]]
    if L[len(L)-1] != 1:
        a += D[L[len(L)-1]][1] 
    return a
'''
def T(R,W): #頂点集合 R = {u1,...,uk}, tまでの待ち時間 W = {w1,...,wk} を受け取って，Score が最小になるような経路をがんばって通った時の時間を出力
    if R == set():
        return 0
    else:
        Req_list = list(R)
        WT = list(W)
        t_path = 0 
        active_random = []      
        active_path= [1]
        k = len(Req_list)
        Score = float["inf"]

        #行列の作成
        Q = [[0 for i in range(k)] for j in range(k)]
        for i in range(k):
            for j in range(k):
                if j <= i:
                    Q[i][j] = k-i
                else:
                    Q[i][j] = k-j
        #乱数の作成
        for s in range(k):
            rand = random.sample(range(k), k=k)

            #x の生成
            x = [0 for i in range(k)]
            for i in range(k):
                if i == 0:
                    x[i] = D[1][Req_list[rand[0]]]
                else:
                    x[i] = D[Req_list[rand[i-1]]][Req_list[rand[i]]]
            #cの生成
            c = [0 for i in range(k)]
            for i in range(k):
                if i == 0:
                    c[k-i-1] = WT[k-i-1]
                else:
                    c[k-i-1] = c[k-i] + WT[k-i-1]
            if Score < f(x,Q,c):
                Score = f(x,Q,c)
                active_random = rand

        #active_path の作成
        for i in range(k):
            active_path.append(Req_list[active_random[i]])
        active_path.append(1)

        #t_path の計算
        for i in range(len(active_path)):
            if i != 0:
                t_path += D[active_path[i-1]][active_path[i]]

        return t_path
'''

'''    
        while Req_list != []:
            x = 0
            u = 0
            for i in range(len(Req_list)):
                if i == 0:
                    x = D[active_path_last][Req_list[0]]
                    u = Req_list[0]
                elif x > D[active_path_last][Req_list[i]]:
                    x = D[active_path_last][Req_list[i]]
                    u = Req_list[i]
            Req_list.remove(u)
            active_path_last = u
            t_path += x
        t_path += D[active_path_last][1]
        active_path_last = 1 # 不要
        return t_path
'''
        
'''       
timeA_time = time.time()
tochuA =timeA_time-starttime
'''


#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)
    W = Wt(t_start,t)
    Req2 = Req.copy()
    t_start = t
    
    #この時点で，リクエストを1個以上もっているか，または t= T_max-1


    k = len(Req)
    #行列の作成
    Q = [[0 for i in range(k)] for j in range(k)]
    for i in range(k):
        for j in range(k):
            if j <= i:
                Q[i][j] = k-i
            else:
                Q[i][j] = k-j

    '''
    print("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
    print("リクエスト数", k)
    '''




    #貪欲法を実行

    active_path2 = [1]

    while Req2 != []:
        x = 0
        u = 0
        for i in range(len(Req2)):
            if i == 0:
                x = D[active_path2[-1]][Req2[0]]
                u = Req2[0]
            elif x > D[active_path2[-1]][Req2[i]]:
                x = D[active_path2[-1]][Req2[i]]
                u = Req2[i]
        Req2.remove(u)
        active_path2.append(u)
    active_path2.append(1)

    t_path2 = dist(active_path2)
    active_req2 = active_path2[1:len(active_path2)]

    '''
    print('貪欲法でのパス',active_path2)
    
    
    print("貪欲法でのパスのコスト",score(active_req2) )
    print("貪欲法でのパスのきょり",t_path2 )
    '''
    

    #2-opt の実行
    now_list = active_req2.copy()

    t1 = time.time()
    t2 = t1

    while True:
        flag = False
        Score_now = score(now_list)
        for i in range(k-1):
            for r in range(k-i-1):
                j = r + i + 1
                new_list = opt2(now_list,i,j)
                if Score_now > score(new_list):
                    now_list = new_list.copy()
                    flag = True
                t2 = time.time()
                if t2 - t1 > 3:
                    flag = False
                    break
            else:
                continue
            break

        if flag == False:
            break

    '''
    else:
        while True:
            flag = 0
            Score_now = score(now_list)
            for i in range(k-1):
                for r in range(k-i-1):
                    j = r + i + 1
                    new_list = opt2(now_list,i,j)
                    if Score_now > score(new_list):
                        count +=1
                        now_list = new_list.copy()
                        flag = 1
                        
            if (flag == 0) or (count > 1):
                break
    '''



    #active_path の作成
    active_path= [1]    
    for i in range(k):
        active_path.append(now_list[i])
    active_path.append(1)

    #t_path の計算
    t_path = dist(active_path)

    '''
    print("2-optしたあとのパス",active_path)
    
    print("2-optしたあとのパスのコスト", score(now_list))

    print("2-optしたあとのパスのきょり", t_path)
    '''
    

    #active-path から real-path を作成
    real_path = []

    for i in range(len(active_path)):
        if i != 0:
            if real_path == []:
                real_path =real_path + Shortest_path(active_path[i-1],active_path[i])
            else:
                real_path.pop(-1)
                real_path =real_path + Shortest_path(active_path[i-1],active_path[i])

    t += t_path

    #real_pathからRootを作成
    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]]):
                if (real_path[j] != 1) or (real_path[j+1] != 1):
                    Root.append(real_path[j+1])




#Root から最終出力を生成
L = len(Root)

for i in range(T_max):
    if i < len(Root):
        print(Root[i])
    else:
        print(-1)
'''
endtime = time.time()
elapsed_time = endtime-starttime
print("最短距離行列とか求めるまでの時間",tochuA)
print("計算時間",elapsed_time)
'''



Fixed submission:
#頂点数と辺数を取得
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)
'''

Buggy python submission (verdict: Runtime Error):
import time
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

'''
starttime = time.time()
'''

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

#隣接行列を作成 (辺がないところは 0，便宜上，(n+1)×(n+1)行列をつくっている)
A = [[float("inf") 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を作成する
D = [[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] = float("inf")
            else: D[i][j] = A[i][j] #辺があるところはその辺の長さ

D1,Prev = floyd_warshall(D,directed=False,return_predecessors=True)   #最短距離を求める(追記を参照)
for i in range(vertex_number+1):
    for j in range(vertex_number+1):
        if D1[i][j] != float("inf"):
            D[i][j] = int(D1[i][j])



def Shortest_path(i,j): #iからj への最短経路をリストとして出力
    SP = [j]
    x = Prev[i][j]
    while (x != i) and (x > 0):
        SP.insert(0,x)
        x = Prev[i][x]
    SP.insert(0,i)
    return SP
'''
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 の間に発生したリクエストの頂点をかぶりをなくして出力
    R = set()
    if a == b: #a=b ならば {} を出力
        return R
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                R.add(info[i+a+1][2])
        return R


def t_first(t): #時刻 t 以降にはじめて発生したリクエストの時刻を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    return time

def v_first(t): #時刻 t 以降にはじめて発生したリクエストの頂点を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    if time < T_max-1:
        return info[time][2]
    else:
        return 1
    
def T(*args): #頂点集合 args[0],...,args[k-1] を受け取って，それらを貪欲に通った時にかかる時間を計算
    if args == set():
        return 0
    else:
        Req_list = list(args)
        t_path = 0       
        active_path_last = 1
        while Req_list != []:
            x = 0
            u = 0
            for i in range(len(Req_list)):
                if i == 0:
                    x = D[active_path_last][Req_list[0]]
                    u = Req_list[0]
                elif x > D[active_path_last][Req_list[i]]:
                    x = D[active_path_last][Req_list[i]]
                    u = Req_list[i]
            Req_list.remove(u)
            active_path_last = u
            t_path += x
        t_path += D[active_path_last][1]
        active_path_last = 1 # 不要
        return t_path
        
'''       
timeA_time = time.time()
tochuA =timeA_time-starttime
'''


#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

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

    else:
        Req = Request(t_start,t)
        
    t_start = t
    
    #この時点で，リクエストを1個以上もっているか，または t= T_max-1

    

    if t < 0.95*T_max:
        while True :   
            '''
            print("Request",Req)
            '''

            T1 = T(*Req)

            if t+T1 > T_max -1:
                break
            else:
                Next_Req = Request(t,t+T1)
                if Next_Req == set():
                    break
                else:                    
                    T2 = T(*Next_Req)
                    t_1 = t_first(t)
                    Delta_t1 = t_1 - t

                    v_1 = v_first(t)
                    V3 = Req.copy()
                    V3.add(v_1)
                    V4 = Next_Req.copy()
                    V4.discard(v_1)

                    T3 = T(*V3)
                    T4 = T(*V4)
                    if Delta_t1+T3+T4 < T1 + T2:           
                        for i in range(Delta_t1):
                            Root.append(-1)
                        Req.add(v_1)
                        t = t_1
                        t_start = t
                    else:
                        break


    Req_list = list(Req)
    t_path = 0       
    active_path_last = 1
    real_path = []
    while Req_list != []:
        #貪欲におけるactive_path_lastから次の頂点 u と，active_path_lastからuまでの距離x を決定
        x = 0
        u = 0
        for i in range(len(Req_list)):
            if i == 0:
                x = D[active_path_last][Req_list[0]]
                u = Req_list[0]
            elif x > D[active_path_last][Req_list[i]]:
                x = D[active_path_last][Req_list[i]]
                u = Req_list[i]

        #real-path の更新
        if real_path == []:
            real_path =real_path + Shortest_path(active_path_last,u)
        else:
            real_path.pop(-1)
            real_path =real_path + Shortest_path(active_path_last,u)

        Req_list.remove(u)
        t_path += x
        active_path_last = u

    t_path += D[active_path_last][1]

    #real-path の更新 (1へかえる)
    if real_path == []:
        real_path =real_path + Shortest_path(active_path_last,1)
    else:
        real_path.pop(-1)
        real_path =real_path + Shortest_path(active_path_last,1)

    t += t_path

    '''
    print("active-path", active_path)
    '''
    
    #real_pathからRootを作成
    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]]):
                if (real_path[j] != 1) or (real_path[j+1] != 1):
                    Root.append(real_path[j+1])
    '''
    print("Root", Root)
    '''

#Root から最終出力を生成
L = len(Root)

for i in range(T_max):
    if i < len(Root):
        print(Root[i])
    else:
        print(-1)
'''
for i in range(T_max):
    if (i < L) and (i != T_max-1):
        print(Root[i])
    elif (i < L) and (i == T_max-1) :
        print(Root[i],end = "")
    elif (i >= L) and (i != T_max-1):
        print(-1)
    elif (i >= L) and (i == T_max-1):
        print(-1,end = "")


endtime = time.time()
elapsed_time = endtime-starttime
print("最短距離行列とか求めるまでの時間",tochuA)
print("計算時間",elapsed_time)
'''


'''
for i in range(T_max):
    print(-1)
'''

Fixed submission:
#頂点数と辺数を取得
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)
'''

Buggy python submission (verdict: Runtime Error):
import time
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix

starttime = time.time()


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

#隣接行列を作成 (辺がないところは 0，便宜上，(n+1)×(n+1)行列をつくっている)
A = [[float("inf") 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を作成する
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] = float("inf")
            else: D[i][j] = A[i][j] #辺があるところはその辺の長さ

D1,Prev = floyd_warshall(D,directed=False,return_predecessors=True)   #最短距離を求める(追記を参照)
for i in range(vertex_number+1):
    for j in range(vertex_number+1):
        if D1[i][j] != float("inf"):
            D[i][j] = int(D1[i][j])



def Shortest_path(i,j): #iからj への最短経路をリストとして出力
    SP = [j]
    x = Prev[i][j]
    while (x != i) and (x > 0):
        SP.insert(0,x)
        x = Prev[i][x]
    SP.insert(0,i)
    return SP
'''
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 の間に発生したリクエストの頂点をかぶりをなくして出力
    R = set()
    if a == b: #a=b ならば {} を出力
        return R
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                R.add(info[i+a+1][2])
        return R


def t_first(t): #時刻 t 以降にはじめて発生したリクエストの時刻を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    return time

def v_first(t): #時刻 t 以降にはじめて発生したリクエストの頂点を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    if time < T_max-1:
        return info[time][2]
    else:
        return 1
    
def T(*args): #頂点集合 args[0],...,args[k-1] を受け取って，それらを貪欲に通った時にかかる時間を計算
    if args == set():
        return 0
    else:
        Req_list = list(args)
        t_path = 0       
        active_path_last = 1
        while Req_list != []:
            x = 0
            u = 0
            for i in range(len(Req_list)):
                if i == 0:
                    x = D[active_path_last][Req_list[0]]
                    u = Req_list[0]
                elif x > D[active_path_last][Req_list[i]]:
                    x = D[active_path_last][Req_list[i]]
                    u = Req_list[i]
            Req_list.remove(u)
            active_path_last = u
            t_path += x
        t_path += D[active_path_last][1]
        active_path_last = 1 # 不要
        return t_path
        
        
timeA_time = time.time()
tochuA =timeA_time-starttime



#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

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

    else:
        Req = Request(t_start,t)
        
    t_start = t
    
    #この時点で，リクエストを1個以上もっているか，または t= T_max-1

    

    if t < 0.95*T_max:
        counter = 0
        while (True) and (counter <5):   
            '''
            print("Request",Req)
            '''

            T1 = T(*Req)

            if t+T1 > T_max -1:
                break
            else:
                Next_Req = Request(t,t+T1)
                if Next_Req == set():
                    break
                else:                    
                    T2 = T(*Next_Req)
                    t_1 = t_first(t)
                    Delta_t1 = t_1 - t

                    v_1 = v_first(t)
                    V3 = Req.copy()
                    V3.add(v_1)
                    V4 = Next_Req.copy()
                    V4.discard(v_1)

                    T3 = T(*V3)
                    T4 = T(*V4)
                    if Delta_t1+T3+T4 < T1 + T2:           
                        for i in range(Delta_t1):
                            Root.append(-1)
                        Req.add(v_1)
                        t = t_1
                        t_start = t
                        counter += 1
                    else:
                        break


    Req_list = list(Req)
    t_path = 0       
    active_path_last = 1
    real_path = []
    while Req_list != []:
        #貪欲におけるactive_path_lastから次の頂点 u と，active_path_lastからuまでの距離x を決定
        x = 0
        u = 0
        for i in range(len(Req_list)):
            if i == 0:
                x = D[active_path_last][Req_list[0]]
                u = Req_list[0]
            elif x > D[active_path_last][Req_list[i]]:
                x = D[active_path_last][Req_list[i]]
                u = Req_list[i]

        #real-path の更新
        if real_path == []:
            real_path =real_path + Shortest_path(active_path_last,u)
        else:
            real_path.pop(-1)
            real_path =real_path + Shortest_path(active_path_last,u)

        Req_list.remove(u)
        t_path += x
        active_path_last = u

    t_path += D[active_path_last][1]

    #real-path の更新 (1へかえる)
    if real_path == []:
        real_path =real_path + Shortest_path(active_path_last,1)
    else:
        real_path.pop(-1)
        real_path =real_path + Shortest_path(active_path_last,1)

    t += t_path

    '''
    print("active-path", active_path)
    '''
    
    #real_pathからRootを作成
    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]]):
                if (real_path[j] != 1) or (real_path[j+1] != 1):
                    Root.append(real_path[j+1])
    '''
    print("Root", Root)
    '''

#Root から最終出力を生成

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

'''
endtime = time.time()
elapsed_time = endtime-starttime
print("最短距離行列とか求めるまでの時間",tochuA)
print("計算時間",elapsed_time)
'''


'''
for i in range(T_max):
    print(-1)
'''

Fixed submission:
#頂点数と辺数を取得
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)
'''

Buggy python submission (verdict: Time Limit Exceeded):

#頂点数と辺数を取得
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
'''

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


def t_first(t): #時刻 t 以降にはじめて発生したリクエストの時刻を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    return time

def v_first(t): #時刻 t 以降にはじめて発生したリクエストの頂点を出力
    time = t+1
    while (info[time] == [0]) and (time != T_max - 1):
        time += 1
    if time < T_max-1:
        return info[time][2]
    else:
        return 1
    
def T(*args): #頂点集合 args[0],...,args[k-1] を受け取って，それらを貪欲に通った時にかかる時間を計算
    if args == set():
        return 0
    else:
        B = list(args)
        Req_list = B[:]
        t_path = 0       
        active_path = [1]
        while Req_list != []:
            x = 0
            u = 0
            for i in range(len(Req_list)):
                if i == 0:
                    x = D[active_path[-1]][Req_list[0]]
                    u = Req_list[0]
                elif x > D[active_path[-1]][Req_list[i]]:
                    x = D[active_path[-1]][Req_list[i]]
                    u = Req_list[i]
            Req_list.remove(u)
            active_path.append(u)
            t_path += x
        t_path += D[active_path[-1]][1]
        active_path.append(1)
        return t_path
        
        
        
#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

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

    else:
        Req = Request(t_start,t)
        
    t_start = t
    
    #この時点で，リクエストを1個以上もっているか，または t= T_max-1

    

    if t < 0.95*T_max:
        
        while True:   
            '''
            print("Request",Req)
            '''
            T1 = T(*Req)
            if t+T1 > T_max -1:
                break
            else:
                Next_Req = Request(t,t+T1)
                if Next_Req == set():
                    break
                else:                    
                    T2 = T(*Next_Req)
                    t_1 = t_first(t)
                    Delta_t1 = t_1 - t

                    v_1 = v_first(t)
                    V3 = Req.copy()
                    V3.add(v_1)
                    V4 = Next_Req.copy()
                    V4.discard(v_1)

                    T3 = T(*V3)
                    T4 = T(*V4)
                    if Delta_t1+T3+T4 < T1 + T2:           
                        for i in range(Delta_t1):
                            Root.append(-1)
                        Req.add(v_1)
                        t = t_1
                        t_start = t
                    else:
                        break


    K = list(Req)
    Req_list = K[:]
    t_path = 0       
    active_path = [1]
    real_path = []
    while Req_list != []:
        x = 0
        u = 0
        for i in range(len(Req_list)):
            if i == 0:
                x = D[active_path[-1]][Req_list[0]]
                u = Req_list[0]
            elif x > D[active_path[-1]][Req_list[i]]:
                x = D[active_path[-1]][Req_list[i]]
                u = Req_list[i]
        Req_list.remove(u)
        active_path.append(u)
        t_path += x
    t_path += D[active_path[-1]][1]
    active_path.append(1)
    t += t_path

    '''
    print("active-path", active_path)
    '''
    
    
    #active_pathからreal_pathを作成
    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])
    #real_pathからRootを作成
    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]]):
                if (real_path[j] == 1) and (real_path[j+1] == 1):
                    Root.append(-1)
                else:
                    Root.append(real_path[j+1])
    '''
    print("Root", Root)
    '''

#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)
'''

Fixed submission:
#頂点数と辺数を取得
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)
'''

Buggy python submission (verdict: Runtime Error):
#頂点数と辺数を取得
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])
''''
#info から　info_vertex を作成
for i in range(len(Req)): #Request から　Visit を作成 
    if Req[i][2] not in Visit:
        Visit.append(Req[i][2])

#フロイド・ワーシャル法
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


#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

while t < T_max-1:
    Req = []
    Visit = []
    if Request(t_start,t) == []:
        counter = 0
        while (info[t] == [0]) and (t != T_max - 1):
            t += 1
            counter += 1
            Root.append(-1)
        Req.append(info[t])
        t_start = t
    else:
        Req = Request(t_start,t)
        t_start = t
        
    if Req != [0]:
        
        for i in range(len(Req)): #Request から　Visit を作成 
            if Req[i][2] not in Visit:
                Visit.append(Req[i][2])
                
        t_path = 0       
        active_path = [1]
        real_path = []
        while Visit != []:
            x = 0
            u = 0
            for i in range(len(Visit)):
                if i == 0:
                    x = D[active_path[-1]][Visit[0]]
                    u = Visit[0]
                elif x > D[active_path[-1]][Visit[i]]:
                    x = D[active_path[-1]][Visit[i]]
                    u = Visit[i]
            Visit.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 から最終出力を生成

Time = 0

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

Fixed submission:
#頂点数と辺数を取得
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)
'''

Buggy python submission (verdict: Runtime Error):
#頂点数と辺数を取得
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


#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

while t < T_max-1:
    Req = []
    Visit = []
    if Request(t_start,t) == []:
        counter = 0
        while (info[t] == [0]) and (t != T_max - 1):
            t += 1
            counter += 1
            Root.append(-1)
        Req.append(info[t])
        t_start = t
    else:
        Req = Request(t_start,t)
        t_start = t
        
    if Req != [0]:
        
        for i in range(len(Req)): #Request から　Visit を作成 
            if Req[i][2] not in Visit:
                Visit.append(Req[i][2])
                
        t_path = 0       
        active_path = [1]
        real_path = []
        while Visit != []:
            x = 0
            u = 0
            for i in range(len(Visit)):
                if i == 0:
                    x = D[active_path[-1]][Visit[0]]
                    u = Visit[0]
                elif x > D[active_path[-1]][Visit[i]]:
                    x = D[active_path[-1]][Visit[i]]
                    u = Visit[i]
            Visit.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 から最終出力を生成

Time = 0

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




Fixed submission:
#頂点数と辺数を取得
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)
'''

Buggy python submission (verdict: Runtime Error):
#頂点数と辺数を取得
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:
        return R
    else:
        for i in range(b-a):
            if info[i+a+1] != [0]:
                R.append(info[i+a+1])
        return R


#Algorithm (貪欲法)

t = 0
t_start = 0
Root = []

while t < T_max:
    Req = []
    Visit = []
    if Request(t_start,t) == []:
        counter = 0
        while info[t] == [0]:
            t += 1
            counter += 1
            if t == T_max:
                Root.append(["wait",counter])
                break
        Req.append(info[t])
        Root.append(["wait",counter])
        t_start = t
    else:
        Req = Request(t_start,t)
        t_start = t
    for i in range(len(Req)): #Request から　Visit を作成 
        if Req[i][2] not in Visit:
            Visit.append(Req[i][2])
    t_path = 0       
    active_path = [1]
    real_path = []
    while Visit != []:
        x = 0
        u = 0
        for i in range(len(Visit)):
            if i == 0:
                x = D[active_path[-1]][Visit[0]]
                u = Visit[0]
            elif x > D[active_path[-1]][Visit[i]]:
                x = D[active_path[-1]][Visit[i]]
                u = Visit[i]
        Visit.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からreal_path を作成
    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])
    Root.append(real_path)

#Root から最終出力を生成

Time = 0

for i in range(len(Root)):
    if Root[i][0] == "wait":
        if Root[i][1] != 0:
            for j in range(Root[i][1]):
                print(-1)
                Time += 1
                if Time == T_max:
                    break
            else:
                continue
            break
    else:
        for k in range(len(Root[i])):
            if k != len(Root[i])-1:
                for s in range(A[Root[i][k]][Root[i][k+1]]):
                    print(Root[i][k+1])
                    Time += 1
                    if Time == T_max:
                        break
                else:
                    continue
                break



Fixed submission:
#頂点数と辺数を取得
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)
'''