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

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

# グラフを構築
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)

def tsp():
    """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を焼きなまし法で決める
    T = 100000
    cool = 0.99999
    cnt = 0
    best_score = total_cost
    best_route = route[0:]
    score = total_cost

    while cnt < 5000000:
        cnt += 1
        #スワップする点を選択
        ind1 = random.randrange(0, n)
        ind2 = random.randrange(0, n)
        while True:
            if ind1 == ind2:
                ind2 = random.randrange(0, 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


route, best_score = tsp()
route2, best_score2 = tsp()
route3, best_score3 = tsp()
if best_score > best_score2:
    route = route2
    best_score = best_score2
if best_score > best_score3:
    route = route3
    best_score = best_score3

# ans: スタートから全部の頂点を通ってスタートに帰るときのコマンド
ans = []
for i in range(n):
    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)


times = (t_max) // len(ans)
nokori = (t_max) - times * len(ans)

for _ in range(nokori):
    print(-1)
cnt = nokori
while True:
    for i in ans:
        cnt += 1
        print(i)
        #f.write(str(i) + "\n")
        if cnt == t_max:
            break
    else:
        continue
    break

Measured memory_bytes: 132532