import random
import time
s_time = time.time()
NAPIER = 2.71828182846
INF = 10**18


def warshall_floid(graph):
    """warshall-floid法: 各頂点から各頂点への最短距離を求める
    重み付きグラフgraphは隣接リストで与えられる
    計算量: O(N^3)
    """
    dp = [[INF]*n for i in range(n)]
    next_ = [[-1]*n for i in range(n)]
    for i in range(n):
        dp[i][i] = 0

    for i in range(n):
        for j, cost in graph[i]:
            dp[i][j] = cost
            dp[j][i] = cost

    for i in range(n):
        for j in range(n):
            next_[i][j] = j

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dp[i][j] > dp[i][k] + dp[k][j]:
                    dp[i][j] = dp[i][k] + dp[k][j]
                    next_[i][j] = next_[i][k]
    return dp, next_


def trace_route(start, goal):
    """warshall-floid法で求めた最短距離を通るための経路を復元する
    計算量: O(N)
    """
    pos = start
    res = []
    while pos != goal:
        res.append(pos)
        pos = next_[pos][goal]
    res.append(goal)
    return res


def tsp(use_v: set):
    """Nearest Neighbourからの焼きなまし2optで地点0から地点0へ巡回する順番を決める
    例) route: 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> 0 のとき
    route = [0, 3, 2, 5, 4, 1, 0]
    """
    
    # 初期値のrouteをNearest Neighbourで決める
    visited = [False] * n
    visited[0] = True

    route = [0]
    pos = 0
    total_cost = 0
    while True:
        kyori = 10**9
        next_pos = -1
        for next_p, cost in enumerate(dp[pos]):
            if visited[next_p]:
                continue
            if cost < kyori:
                kyori = cost
                next_pos = next_p
        if next_pos == -1:
            break
        else:
            visited[next_pos] = True
            route.append(next_pos)
            pos = next_pos
            total_cost += kyori
    total_cost += dp[0][route[-1]]
    route.append(0)
    route_n = len(route) - 1

    # 最も良いrouteを焼きなまし法で決める
    if route_n == n:
        T = 1000000
        cool = 0.99 #0.999995
        cnt = 5000000
        best_score = total_cost
        best_route = route[0:]
        score = total_cost

    #else:
    #    T = 100000000
    #    cool = 0.9
    #    cnt = 0
    #    best_score = total_cost
    #    best_route = route[0:]
    #    score = total_cost

    while cnt < 7000000:
        cnt += 1
        #スワップする点を選択
        ind1 = random.randrange(0, route_n)
        ind2 = random.randrange(0, route_n)
        while True:
            if ind1 == ind2:
                ind2 = random.randrange(0, route_n)
            else:
                break
        if ind1 > ind2:
            ind1, ind2 = ind2, ind1
        
        # スワップする前のコスト
        before_cost = dp[ route[ind1] ][ route[ind1+1] ] + dp[ route[ind2] ][ route[ind2+1] ]
        # スワップした後のコスト
        after_cost = dp[ route[ind1] ][ route[ind2] ] + dp[ route[ind1+1] ][ route[ind2+1] ] 
        # 温度から確率を定義
        p = pow(NAPIER, -abs(before_cost - after_cost) / T)
        # 遷移
        if (after_cost < before_cost or random.random() < p):
            route = route[0:ind1+1] + route[ind1+1:ind2+1][::-1] + route[ind2+1:]
            score = score + after_cost - before_cost
        # ベストスコアを保存しておく
        if score < best_score:
            best_score = score
            best_route = route[0:]
        # 温度を下げる
        T = T * cool
 
        #状態を確認する
        #if cnt % 100000 == 1:
        #    print(cnt, p)

    return best_route, best_score


def strict_tsp(use_v: set):
    """巡回セールスマン問題の厳密解を解く"""
    n_tsp = len(use_v)
    list_tsp = sorted(list(use_v))

    dq = [[INF]*n_tsp for i in range(1 << n_tsp)]
    dq[1 << 0][0] = 0

    next_tsp = [[0]*n_tsp for i in range(1 << n_tsp)]
    for bit_state in range(1 << n_tsp):
        for j in range(n_tsp):
            next_tsp[bit_state][j] = -1

    for bit_state in range(1 << n_tsp):
        for i in range(n_tsp):
            # bit_stateにiが含まれてない場合は飛ばす
            if not (bit_state >> i) & 1:
                continue
            for j in range(n_tsp):
                # bit_stateにjが含まれている場合は飛ばす
                if ((bit_state >> j) & 1):
                    continue
                if dq[bit_state|(1 << j)][j] > dq[bit_state][i] + dp[list_tsp[i]][list_tsp[j]]:
                    dq[bit_state|(1 << j)][j] = dq[bit_state][i] + dp[list_tsp[i]][list_tsp[j]]
                    next_tsp[bit_state|(1 << j)][j] = i

    min_cost = INF
    last_pos = -1
    for i in range(0, n_tsp)[::-1]:
        if dq[(1 << n_tsp) - 1][i] + dp[0][list_tsp[i]] < min_cost:
            min_cost = dq[(1 << n_tsp) - 1][i] + dp[0][list_tsp[i]] 
            last_pos = i

    pos = 0
    res = [0, list_tsp[last_pos]]
    bit_state = (1 << n_tsp) - 1
    while True:
        res.append(list_tsp[next_tsp[bit_state][last_pos]])
        tmp = bit_state
        bit_state -= (1 << last_pos)
        last_pos = next_tsp[tmp][last_pos]
        if res[-1] == 0:
            break

    return res, min_cost


# 値を入力する
n, m = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
t_max = int(input())
query = [None] * t_max
for i in range(t_max):
    tmp = int(input())
    if tmp == 0:
        continue
    else:
        query[i] = list(map(int, input().split()))

# グラフを構築
graph = [[] for i in range(n)]
for a, b, cost in info:
    a -= 1
    b -= 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))

# 最短距離を求める
dp, next_ = warshall_floid(graph)

#全部通るときの最短ルート
tmp_set = set([i for i in range(n)])
all_route, all_cost = tsp(tmp_set)


start_ti = 1
prev_start_ti = 0
tmp_set = set([0])
ans = []
flag = True
while flag:
    for i in range(prev_start_ti, start_ti):
        if t_max <= i:
            flag = False
            break
        if query[i] is None:
            continue
        tmp_set.add(query[i][1] - 1)

    # 荷物が何も無い時
    if len(tmp_set) == 1:
        ans.append(-1)
        start_ti += 1
        prev_start_ti = start_ti - 1
        continue
    # 配達箇所が20個以下の時 -> 厳密解を解く    
    elif len(tmp_set) <= 20:
        route, cost = strict_tsp(tmp_set)
    # それ以外 -> 焼きなまし法   
    else:
        route, cost = all_route, all_cost 

    for i in range(len(route) - 1):
        pos = route[i]
        next_pos = route[i+1]
        tmp = trace_route(pos, next_pos)
        for j in range(len(tmp)-1):
            for _ in range(dp[tmp[j]][tmp[j+1]]):
                ans.append(tmp[j+1] + 1)

    start_ti += cost
    prev_start_ti = start_ti - cost

for i in ans[0:t_max]:
    print(i)


Measured memory_bytes: 177624