Hitachi Hokudai Labo & Hokkaido University Contest 2019-1 - Problem A

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

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

	def dijkstra(s):
		d = [float('inf')] * n
		pre = [None] * n
		d[s] = 0
		q = [(0, s)]
		while q:
			(dx, x) = heappop(q)
			for (y, w) in v[x]:
				nd = dx + w
				if nd < d[y]:
					d[y] = nd
					pre[y] = x
					heappush(q, (nd, y))
		path = [[i] for i in range(n)]
		for i in range(n):
			while path[i][-1] != s:
				path[i].append(pre[path[i][-1]])
			path[i] = path[i][::-1][1:]
		return (d, path)
	(n, m) = LI()
	v = [[] for i in range(n)]
	for i in range(m):
		(a, b, d) = LI()
		a -= 1
		b -= 1
		v[a].append((b, d))
		v[b].append((a, d))
	d = [None] * n
	path = [None] * n
	for s in range(n):
		(d[s], path[s]) = dijkstra(s)
	t = I()
	q = deque()
	for i in range(t):
		N = I()
		if N == 0:
			continue
		(a, y) = LI()
		y -= 1
		q.append((i, y))
	x = 0
	dx = 0
	dy = 0
	query = deque()
	dst = 0
	go = []
	f = 0
	time = [None] * n
	fl = [0] * n
	for i in range(t):
		while go and (not fl[go[0]]):
			go.pop(0)
		while q and q[0][0] == i:
			(k, l) = q.popleft()
			query.append(l)
			if time[l] == None:
				time[l] = k
		if not f:
			if x == 0:
				if not query:
					print(-1)
				else:
					f = 1
					while query:
						dst = query.popleft()
						go.append(dst)
						fl[dst] = 1
					go = list(set(go))
					go.sort(key=lambda a: time[a] + d[x][a])
					time = [None] * n
					dst = go.pop(0)
					p = [i for i in path[x][dst]]
					y = p.pop(0)
					print(y + 1)
					dx = 1
					dy = d[x][y]
					if dx == dy:
						fl[y] = 0
						x = y
						dx = 0
						if x == dst:
							if go:
								dst = go.pop(0)
								p = [i for i in path[x][dst]]
								y = p.pop(0)
								dy = d[x][y]
							else:
								f = 0
								dst = 0
								p = [i for i in path[x][dst]]
								y = p.pop(0)
								dy = d[x][y]
						else:
							y = p.pop(0)
							dy = d[x][y]
			else:
				print(y + 1)
				dx += 1
				if dx == dy:
					fl[y] = 0
					x = y
					dx = 0
					if p:
						y = p.pop(0)
						dy = d[x][y]
		else:
			print(y + 1)
			dx += 1
			if dx == dy:
				fl[y] = 0
				x = y
				dx = 0
				if x == dst:
					if go:
						dst = go.pop(0)
						p = [i for i in path[x][dst]]
						y = p.pop(0)
						dy = d[x][y]
					else:
						f = 0
						dst = 0
						p = [i for i in path[x][dst]]
						y = p.pop(0)
						dy = d[x][y]
				else:
					y = p.pop(0)
					dy = d[x][y]
	return
solve()


import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False
MAXVISIT = 400
SPLITTHR = 100

def ddprint(x):
	if DBG:
		print(x)
		sys.stdout.flush()

def trigger():
	return len(pendreq) > 0

def nxtnode():
	global lastnd, workreq, nxtndary
	tgt = workreq[0] if len(workreq) > 0 else 1
	return nxtndary[lastnd][tgt]

def atdepot():
	return lastnd == 1 and distfromlast == 0

def stay():
	print(-1)
	sys.stdout.flush()

def readput():
	n = inn()
	for i in range(n):
		inn()

def readverd():
	v = input().strip()
	if v != 'OK':
		exit()
	readput()

def move():
	global distfromlast, lastnd, workreq
	nxtnd = nxtnode()
	print(nxtnd)
	sys.stdout.flush()
	distfromlast += 1
	if distfromlast == dist[lastnd][nxtnd]:
		distfromlast = 0
		if len(workreq) > 0 and nxtnd == workreq[0]:
			del workreq[0]
		lastnd = nxtnd

def ufinit(n):
	global ufary, ufrank
	ufary = [i for i in range(n)]
	ufrank = [0] * n

def ufroot(i):
	p = ufary[i]
	if p == i:
		return p
	q = ufroot(p)
	ufary[i] = q
	return q

def ufmerge(i, j):
	global ufary, ufrank
	ri = ufroot(i)
	rj = ufroot(j)
	if ri == rj:
		return
	if ufrank[ri] > ufrank[rj]:
		ufary[rj] = ri
	else:
		ufary[ri] = rj
		if ufrank[ri] == ufrank[rj]:
			ufrank[rj] += 1

def setwork():
	global pendreq, workreq, lastside
	visset = set([x[1] for x in pendreq]) | set(workreq)
	vislist = list(visset)
	vv = len(vislist)
	if vv == 1:
		workreq = vislist
		pendreq = []
		return
	if vv > SPLITTHR:
		vislist = [x for x in vislist if x in gr[lastside]]
		vv = len(vislist)
		lastside = 1 - lastside
		pendreq = [x for x in pendreq if x[1] not in vislist]
	else:
		pendreq = []
	e = {}
	f = {}
	for x in vislist:
		e[x] = []
	ufinit(V + 1)
	for _ in range(vv - 1):
		mx = -1
		for i in e:
			for j in e:
				if ufroot(i) == ufroot(j):
					continue
				df = dist[i][1] + dist[1][j] - dist[i][j]
				if df > mx:
					mx = df
					mxi = i
					mxj = j
		i = mxi
		j = mxj
		e[i].append(j)
		e[j].append(i)
		ufmerge(i, j)
		if len(e[i]) == 2:
			f[i] = e[i]
			del e[i]
		if len(e[j]) == 2:
			f[j] = e[j]
			del e[j]
	ek = list(e.keys())
	p = ek[0]
	prev = p
	cur = e[p][0]
	workreq = [p, cur]
	for i in range(vv - 2):
		p = cur
		cur = f[p][0]
		if cur == prev:
			cur = f[p][1]
		prev = p
		workreq.append(cur)

def findcorners():
	mx = -1
	for i in range(1, V + 1):
		for j in range(1, V + 1):
			d = dist[i][j]
			if d > mx:
				mx = d
				mxi = i
				mxj = j
	c1 = mxi
	c3 = mxj
	mx = -1
	for i in range(1, V + 1):
		d = dist[i][c1] + dist[i][c3]
		if d > mx:
			mx = d
			mxi = i
	c2 = mxi
	mx = -1
	for i in range(1, V + 1):
		d = dist[i][c1] + dist[i][c3] + dist[i][c2]
		if d > mx:
			mx = d
			mxi = i
	c4 = mxi
	d1 = dist[1][c1]
	d2 = dist[1][c2]
	d3 = dist[1][c3]
	d4 = dist[1][c4]
	if min(d1, d3) < min(d2, d4):
		z = (c2, c4)
	else:
		z = (c1, c3)
	a = []
	for i in range(2, V + 1):
		df = dist[i][z[0]] - dist[i][z[1]]
		a.append((df, i))
	a.sort()
	g0 = [x[1] for x in a[:(V - 1) // 2]]
	g1 = [x[1] for x in a[(V - 1) // 2:]]
	return (g0, g1)
ddprint('start')
(V, E) = inm()
es = [[] for i in range(V + 1)]
dist = [[9999] * (V + 1) for i in range(V + 1)]
for i in range(V + 1):
	dist[i][i] = 0
for i in range(E):
	(a, b, c) = inm()
	es[a].append((b, c))
	es[b].append((a, c))
	dist[a][b] = dist[b][a] = c
if DBG:
	for (i, z) in enumerate(es):
		print(str(i) + ' ' + str(z))
for k in range(1, V + 1):
	for i in range(1, V + 1):
		for j in range(1, V + 1):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ddprint('WS done')
nxtndary = [[0] * (V + 1) for i in range(V + 1)]
for i in range(1, V + 1):
	for j in range(1, V + 1):
		if j == i:
			continue
		found = False
		for z in es[i]:
			k = z[0]
			if dist[i][j] == z[1] + dist[k][j]:
				nxtndary[i][j] = k
				found = True
				break
		if not found:
			print('nxtndary ERR')
			exit()
(g0, g1) = findcorners()
gr = [g0, g1]
lastside = 0
F = inl()
if len(F) == 1:
	prob = 1
	tt = F[0]
else:
	prob = 2
	tt = inn()
pendreq = []
workreq = []
lastnd = 1
distfromlast = 0
for t in range(tt):
	if DBG and t > 3400:
		exit()
	n = inn()
	if n == 1:
		(new_id, dst) = inm()
		pendreq.append((new_id, dst))
	if prob == 2:
		readput()
	if atdepot():
		if trigger():
			setwork()
			if len(workreq) > 0:
				move()
			else:
				stay()
		else:
			stay()
	else:
		move()
	if prob == 2:
		readverd()


import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False
MAXVISIT = 400
SPLITTHR = 44
HISTTHR = -1
SPLITTHR4 = 80
HISTTHR4 = 8

def ddprint(x):
	if DBG:
		print(x)
		sys.stdout.flush()

def trigger():
	return len(loadhash) > 0

def nxtnode():
	global lastnd, workreq, nxtndary
	tgt = workreq[0] if len(workreq) > 0 else 1
	return nxtndary[lastnd][tgt]

def atdepot():
	return lastnd == 1 and distfromlast == 0

def stay():
	print(-1)
	sys.stdout.flush()

def readput():
	n = inn()
	for i in range(n):
		inn()

def readverd():
	v = input().strip()
	if v != 'OK':
		exit()
	readput()

def move():
	global distfromlast, lastnd, workreq, pendreq, loadhash
	nxtnd = nxtnode()
	print(nxtnd)
	sys.stdout.flush()
	distfromlast += 1
	if distfromlast == dist[lastnd][nxtnd]:
		distfromlast = 0
		if nxtnd in workreq:
			workreq.remove(nxtnd)
		if nxtnd in loadhash:
			del loadhash[nxtnd]
		if nxtnd == 1:
			for z in pendreq:
				if z[1] not in loadhash:
					loadhash[z[1]] = []
				loadhash[z[1]].append(z[2])
			pendreq = []
		lastnd = nxtnd

def ufinit(n):
	global ufary, ufrank
	ufary = [i for i in range(n)]
	ufrank = [0] * n

def ufroot(i):
	p = ufary[i]
	if p == i:
		return p
	q = ufroot(p)
	ufary[i] = q
	return q

def ufmerge(i, j):
	global ufary, ufrank
	ri = ufroot(i)
	rj = ufroot(j)
	if ri == rj:
		return
	if ufrank[ri] > ufrank[rj]:
		ufary[rj] = ri
	else:
		ufary[ri] = rj
		if ufrank[ri] == ufrank[rj]:
			ufrank[rj] += 1

def setwork():
	global workreq, lastside, loadhash
	visset = set(loadhash.keys()) | set(workreq)
	vislist = list(visset)
	vv = len(vislist)
	if vv == 1:
		workreq = vislist
		return
	if vv > SPLITTHR4 and sum(hist) > HISTTHR4:
		pt = [0, 0, 0, 0]
		for x in vislist:
			suf = 0 if x in gr4[0] else 1 if x in gr4[1] else 2 if x in gr4[2] else 3
			pt[suf] += sum([t - y for y in loadhash[x]])
		mx = max(pt)
		lastside = 0 if mx == pt[0] else 1 if mx == pt[1] else 2 if mx == pt[2] else 3
		vislist = [x for x in vislist if x in gr4[lastside]]
		vv = len(vislist)
	elif vv > SPLITTHR and sum(hist) > HISTTHR:
		pt = [0, 0]
		for x in vislist:
			suf = 0 if x in gr[0] else 1
			pt[suf] += sum([t - y for y in loadhash[x]])
		lastside = 0 if pt[0] >= pt[1] else 1
		vislist = [x for x in vislist if x in gr[lastside]]
		vv = len(vislist)
		lastside = 1 - lastside
	e = {}
	f = {}
	for x in vislist:
		e[x] = []
	ufinit(V + 1)
	for _ in range(vv - 1):
		mx = -1
		for i in e:
			for j in e:
				if ufroot(i) == ufroot(j):
					continue
				df = dist[i][1] + dist[1][j] - dist[i][j]
				if df > mx:
					mx = df
					mxi = i
					mxj = j
		i = mxi
		j = mxj
		e[i].append(j)
		e[j].append(i)
		ufmerge(i, j)
		if len(e[i]) == 2:
			f[i] = e[i]
			del e[i]
		if len(e[j]) == 2:
			f[j] = e[j]
			del e[j]
	ek = list(e.keys())
	p = ek[0]
	prev = p
	cur = e[p][0]
	workreq = [p, cur]
	for i in range(vv - 2):
		p = cur
		cur = f[p][0]
		if cur == prev:
			cur = f[p][1]
		prev = p
		workreq.append(cur)
	acct = t
	prev = 1
	fwdpt = 0
	for i in range(len(workreq)):
		x = workreq[i]
		for y in loadhash[x]:
			fwdpt += acct - y
		acct += dist[prev][x]
		prev = x
	acct = t
	prev = 1
	revpt = 0
	for i in range(len(workreq)):
		x = workreq[len(workreq) - 1 - i]
		for y in loadhash[x]:
			revpt += acct - y
		acct += dist[prev][x]
		prev = x
	if revpt < fwdpt:
		workreq.reverse()

def findcorners():
	mx = -1
	for i in range(1, V + 1):
		for j in range(1, V + 1):
			d = dist[i][j]
			if d > mx:
				mx = d
				mxi = i
				mxj = j
	c1 = mxi
	c3 = mxj
	mx = -1
	for i in range(1, V + 1):
		d = dist[i][c1] + dist[i][c3]
		if d > mx:
			mx = d
			mxi = i
	c2 = mxi
	mx = -1
	for i in range(1, V + 1):
		d = dist[i][c1] + dist[i][c3] + dist[i][c2]
		if d > mx:
			mx = d
			mxi = i
	c4 = mxi
	d1 = dist[1][c1]
	d2 = dist[1][c2]
	d3 = dist[1][c3]
	d4 = dist[1][c4]
	if min(d1, d3) < min(d2, d4):
		z = (c2, c4)
	else:
		z = (c1, c3)
	a = []
	for i in range(2, V + 1):
		df = dist[i][z[0]] - dist[i][z[1]]
		a.append((df, i))
	a.sort()
	g0 = [x[1] for x in a[:(V - 1) // 2]]
	g1 = [x[1] for x in a[(V - 1) // 2:]]
	tricent = 0
	if 3 * d1 < min([d2, d3, d4]):
		tricent = c1
	elif 3 * d2 < min([d1, d3, d4]):
		tricent = c2
	elif 3 * d3 < min([d1, d2, d4]):
		tricent = c3
	elif 3 * d4 < min([d1, d2, d3]):
		tricent = c4
	h0 = []
	h1 = []
	h2 = []
	h3 = []
	if tricent == 0:
		for i in range(2, V + 1):
			d1 = dist[i][c1]
			d2 = dist[i][c2]
			d3 = dist[i][c3]
			d4 = dist[i][c4]
			mn = min([d1, d2, d3, d4])
			if mn == d1:
				h0.append(i)
			elif mn == d2:
				h1.append(i)
			elif mn == d3:
				h2.append(i)
			elif mn == d4:
				h3.append(i)
	else:
		if tricent == c1:
			ccc = [c2, c3, c4]
		elif tricent == c2:
			ccc = [c1, c3, c4]
		elif tricent == c3:
			ccc = [c1, c2, c4]
		else:
			ccc = [c1, c2, c3]
		for i in range(2, V + 1):
			d1 = dist[i][ccc[0]]
			d2 = dist[i][ccc[1]]
			d3 = dist[i][ccc[2]]
			mn = min([d1, d2, d3])
			if mn == d1:
				h0.append(i)
			elif mn == d2:
				h1.append(i)
			else:
				h2.append(i)
	return (g0, g1, h0, h1, h2, h3)
ddprint('start')
(V, E) = inm()
es = [[] for i in range(V + 1)]
dist = [[9999] * (V + 1) for i in range(V + 1)]
for i in range(V + 1):
	dist[i][i] = 0
for i in range(E):
	(a, b, c) = inm()
	es[a].append((b, c))
	es[b].append((a, c))
	dist[a][b] = dist[b][a] = c
if DBG:
	for (i, z) in enumerate(es):
		print(str(i) + ' ' + str(z))
for k in range(1, V + 1):
	for i in range(1, V + 1):
		for j in range(1, V + 1):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ddprint('WS done')
nxtndary = [[0] * (V + 1) for i in range(V + 1)]
for i in range(1, V + 1):
	for j in range(1, V + 1):
		if j == i:
			continue
		found = False
		for z in es[i]:
			k = z[0]
			if dist[i][j] == z[1] + dist[k][j]:
				nxtndary[i][j] = k
				found = True
				break
		if not found:
			print('nxtndary ERR')
			exit()
(g0, g1, h0, h1, h2, h3) = findcorners()
gr = [g0, g1]
gr4 = [h0, h1, h2, h3]
lastside = 0
F = inl()
if len(F) == 1:
	prob = 1
	tt = F[0]
else:
	prob = 2
	tt = inn()
pendreq = []
workreq = []
loadhash = {}
lastnd = 1
distfromlast = 0
hist = []
for t in range(tt):
	if DBG and t > 3400:
		exit()
	n = inn()
	hist.append(n)
	if len(hist) > 20:
		hist = hist[1:]
	if n == 1:
		(new_id, dst) = inm()
		if not atdepot():
			pendreq.append((new_id, dst, t))
		else:
			if dst not in loadhash:
				loadhash[dst] = []
			loadhash[dst].append(t)
	if prob == 2:
		readput()
	if atdepot():
		if trigger():
			setwork()
			if len(workreq) > 0:
				move()
			else:
				stay()
		else:
			stay()
	else:
		move()
	if prob == 2:
		readverd()


import math
[v, e] = list(map(int, input().split()))
chizu = []
for i in range(e):
	chizu.append(list(map(int, input().split())))
tmax = int(input())
info = []
for i in range(tmax):
	kari = []
	nnew = int(input())
	kari.append(nnew)
	for j in range(nnew):
		kari.append(list(map(int, input().split())))
	info.append(kari)
chizukai = [[0 for i in range(v + 1)] for j in range(v + 1)]
for i in range(e):
	chizukai[chizu[i][0]][chizu[i][1]] = chizu[i][2]
	chizukai[chizu[i][1]][chizu[i][0]] = chizu[i][2]

def dijkstra(s, g, chizukai):
	import math
	distance = [float('inf') for i in range(v + 1)]
	distance[s] = 0
	previous_nodes = [-1 for i in range(v + 1)]
	previous_nodes[0] = float('inf')
	unsearched_nodes = list(range(1, v + 1))
	unsearched_nodes.remove(s)
	min_index = s
	mae_index = s
	while len(unsearched_nodes) != 0:
		for i in range(v + 1):
			if chizukai[min_index][i] != 0:
				if distance[i] > distance[min_index] + chizukai[min_index][i]:
					distance[i] = distance[min_index] + chizukai[min_index][i]
					previous_nodes[i] = min_index
		mini = float('inf')
		for i in unsearched_nodes:
			if mini > distance[i]:
				mini = distance[i]
				min_index = i
		unsearched_nodes.remove(min_index)
		mae_index = min_index
	routelist = [g]
	ima = g
	while True:
		routelist.append(previous_nodes[ima])
		ima = previous_nodes[ima]
		if ima == s:
			break
	routelist.reverse()
	kyorilist = []
	for i in range(len(routelist) - 1):
		kyorilist.append(chizukai[routelist[i]][routelist[i + 1]])
	return [routelist, kyorilist]
shirushi = 0
maenode = 1
tuginode = -1
kyori = 0
tansakuzumi = 0
nidai = []
jimusho = []
sindo = 1
for i in range(tmax):
	shirushi = 0
	if kyori == 0:
		for j in range(nidai.count(maenode)):
			nidai.remove(maenode)
	if maenode == 1 and kyori == 0:
		for j in range(len(jimusho)):
			nidai.append(jimusho[j])
		jimusho.clear()
		for j in range(info[i][0]):
			nidai.append(info[i][j + 1][1])
	else:
		for j in range(info[i][0]):
			jimusho.append(info[i][j + 1][1])
	if tansakuzumi == 0:
		if len(nidai) != 0:
			[r, k] = dijkstra(maenode, nidai[0], chizukai)
			tuginode = r[sindo]
			tansakuzumi = 1
		elif maenode != 1:
			[r, k] = dijkstra(maenode, 1, chizukai)
			tuginode = r[sindo]
			tansakuzumi = 1
		else:
			print(-1)
			shirushi = 1
	if shirushi == 0:
		print(tuginode)
	if shirushi == 0:
		kyori += 1
		if kyori == k[sindo - 1]:
			if tuginode == r[-1]:
				kyori = 0
				maenode = tuginode
				tuginode = 0
				tansakuzumi = 0
				sindo = 1
			else:
				kyori = 0
				maenode = tuginode
				tuginode = r[sindo + 1]
				sindo += 1


def warshall_floid(graph):
	n = len(graph)
	INF = 10 ** 18
	dp = [[INF] * 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 k in range(n):
		for i in range(n):
			for j in range(n):
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
	return dp

def trace_route(start, goal):
	pos = start
	ans = []
	while pos != goal:
		ans.append(pos)
		for next_pos in range(n):
			if next_pos != pos and dp[pos][next_pos] + dp[next_pos][goal] == dp[pos][goal]:
				pos = next_pos
				break
	ans.append(goal)
	return ans
(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())
	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 = warshall_floid(graph)
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)
		total_cost += kyori
for i in range(n - 1):
	pos = route[i]
	next_pos = route[i + 1]
for i in range(t_max):
	print(-1)


import sys
from collections import deque
from heapq import heapify, heappop, heappush
from math import sqrt
from itertools import permutations

def root_search(order, cost, wf, V):
	type_num = len(order)
	hold = []
	heapify(hold)
	pre_hold = []
	pre_hold.append((0, '0', set() | order, 0))
	hold_size = 0
	for i in range(type_num):
		for (pre_cost, pre_pass, to_search, pre_id) in pre_hold:
			for key in to_search:
				heappush(hold, (pre_cost + wf[pre_id][key] / sqrt(cost[key][1]), ' '.join([pre_pass, str(key)]), to_search - {key}, key))
				hold_size += 1
		pre_hold = []
		for _ in range(min(hold_size, 3)):
			pre_hold.append(heappop(hold))
		hold = []
		hold_size = 0
	(ans_cost, ans_pass, ans_search, ans_id) = pre_hold[0]
	pass_list = [int(v) for v in ans_pass.split()]
	pass_list.append(0)
	return pass_list

def decide_next_dst(cost, order, current_id, final_dist, store_hold, wf):
	c = store_hold * 1000 / wf[current_id][0]
	for key in order:
		if cost[key][1] * 10000 / wf[current_id][key] > c:
			return final_dist
	return 0

def solve():
	inf = 10000000000
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	edge = dict()
	wf = dict()
	next_id = dict()
	for i in range(V):
		edge[i] = dict()
		wf[i] = dict()
		next_id[i] = dict()
		for j in range(V):
			edge[i][j] = 0 if i == j else inf
			next_id[i][j] = j
			wf[i][j] = 0 if i == j else inf
	for _ in range(E):
		(u, v, d) = map(int, input().split())
		edge[u - 1][v - 1] = d
		edge[v - 1][u - 1] = d
		wf[u - 1][v - 1] = d
		wf[v - 1][u - 1] = d
	for k in range(V):
		for (i, j) in permutations(range(V), 2):
			if wf[i][j] > wf[i][k] + wf[k][j]:
				wf[i][j] = wf[i][k] + wf[k][j]
				next_id[i][j] = next_id[i][k]
	T = int(input())
	order = set()
	stuck_order = set()
	command = dict()
	for t in range(T):
		command[t] = -1
	heading = 0
	dist_left = 0
	final_dist = 0
	driver_hold = 0
	root_pointer = 0
	store_list = [0] * V
	root_list = []
	cost = dict()
	for i in range(V):
		cost[i] = [0, 0]
	store_hold = 0
	for t in range(T):
		N = int(input())
		if N == 1:
			(new_id, dst) = map(int, input().split())
			stuck_order |= {dst - 1}
			store_hold += 1
			store_list[dst - 1] += 1
		if dist_left > 0:
			command[t] = heading + 1
			dist_left -= 1
		else:
			if heading == 0:
				if store_hold == driver_hold == 0:
					continue
				else:
					order |= stuck_order
					driver_hold += store_hold
					for key in order:
						cost[key][1] += 0.5 * cost[key][0] + store_list[key]
						cost[key][0] += store_list[key]
						store_list[key] = 0
					stuck_order = set()
					store_hold = 0
					root_list = root_search(order, cost, wf, V)
					current_id = heading = final_dist = 0
					root_pointer = 0
					root_size = len(root_list)
			if heading in order:
				order.remove(heading)
				driver_hold -= cost[heading][0]
				cost[heading] = [0, 0]
			current_id = heading
			if current_id == final_dist:
				for j in range(root_pointer, root_size - 1):
					if cost[root_list[j + 1]][0] > 0:
						final_dist = root_list[j + 1]
						root_pointer = j + 1
						if current_id > 0 and store_hold > 0:
							final_dist = decide_next_dst(cost, order, current_id, final_dist, store_hold, wf)
						break
				else:
					final_dist = 0
			heading = next_id[current_id][final_dist]
			dist_left = edge[current_id][heading] - 1
			command[t] = heading + 1
	for i in range(T):
		print(command[i])
	return 0
solve()


import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False
PROBL = 1
MAXVISIT = 400

def ddprint(x):
	if DBG:
		print(x)
		sys.stdout.flush()

def trigger():
	return len(pendreq) > 0

def nxtnode():
	global lastnd, workreq, nxtndary
	tgt = workreq[0] if len(workreq) > 0 else 1
	return nxtndary[lastnd][tgt]

def atdepot():
	return lastnd == 1 and distfromlast == 0

def stay():
	print(-1)
	sys.stdout.flush()

def readput():
	n = inn()
	for i in range(n):
		inn()

def readverd():
	v = input().strip()
	if v != 'OK':
		exit()
	readput()

def move():
	global distfromlast, lastnd, workreq
	nxtnd = nxtnode()
	print(nxtnd)
	sys.stdout.flush()
	distfromlast += 1
	if distfromlast == dist[lastnd][nxtnd]:
		distfromlast = 0
		if len(workreq) > 0 and nxtnd == workreq[0]:
			del workreq[0]
		lastnd = nxtnd

def ufinit(n):
	global ufary, ufrank
	ufary = [i for i in range(n)]
	ufrank = [0] * n

def ufroot(i):
	p = ufary[i]
	if p == i:
		return p
	q = ufroot(p)
	ufary[i] = q
	return q

def ufmerge(i, j):
	global ufary, ufrank
	ri = ufroot(i)
	rj = ufroot(j)
	if ri == rj:
		return
	if ufrank[ri] > ufrank[rj]:
		ufary[rj] = ri
	else:
		ufary[ri] = rj
		if ufrank[ri] == ufrank[rj]:
			ufrank[rj] += 1

def setwork():
	global pendreq, workreq
	vislist = set([x[1] for x in pendreq]) | set(workreq)
	vv = len(vislist)
	pendreq = []
	if vv == 1:
		workreq = list(vislist)
		return
	e = {}
	f = {}
	for x in vislist:
		e[x] = []
	ufinit(V + 1)
	for _ in range(vv - 1):
		mx = -1
		for i in e:
			for j in e:
				if ufroot(i) == ufroot(j):
					continue
				df = dist[i][1] + dist[1][j] - dist[i][j]
				if df > mx:
					mx = df
					mxi = i
					mxj = j
		i = mxi
		j = mxj
		e[i].append(j)
		e[j].append(i)
		ufmerge(i, j)
		if len(e[i]) == 2:
			f[i] = e[i]
			del e[i]
		if len(e[j]) == 2:
			f[j] = e[j]
			del e[j]
	ek = list(e.keys())
	p = ek[0]
	prev = p
	cur = e[p][0]
	workreq = [p, cur]
	for i in range(vv - 2):
		p = cur
		cur = f[p][0]
		if cur == prev:
			cur = f[p][1]
		prev = p
		workreq.append(cur)

def setwork1():
	global pendreq, workreq
	oldest = pendreq[0][1]
	pendset = set([x[1] for x in pendreq])
	sortq = []
	for i in [0, 1]:
		q = []
		base = 1 if i == 1 else oldest
		for x in pendset:
			q.append((dist[base][x], x))
		q.sort(reverse=True)
		sortq.append(q)
	vislist = []
	while len(vislist) < MAXVISIT and (len(sortq[0]) > 0 or len(sortq[1]) > 0):
		for j in [0, 1]:
			if len(sortq[j]) == 0:
				continue
			(d, x) = sortq[j].pop()
			if x in vislist or x in workreq:
				continue
			vislist.append(x)
	prev = 1
	while len(vislist) > 0:
		mn = 9999
		for (i, x) in enumerate(vislist):
			d = dist[prev][x]
			if d < mn:
				mn = d
				mni = i
		mnx = vislist[mni]
		workreq.append(mnx)
		del vislist[mni]
		prev = mnx
	pendreq = [x for x in pendreq if x[1] not in workreq]
ddprint('start')
prob = PROBL
(V, E) = inm()
es = [[] for i in range(V + 1)]
dist = [[9999] * (V + 1) for i in range(V + 1)]
for i in range(V + 1):
	dist[i][i] = 0
for i in range(E):
	(a, b, c) = inm()
	es[a].append((b, c))
	es[b].append((a, c))
	dist[a][b] = dist[b][a] = c
if DBG:
	for (i, z) in enumerate(es):
		print(str(i) + ' ' + str(z))
for k in range(1, V + 1):
	for i in range(1, V + 1):
		for j in range(1, V + 1):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ddprint('WS done')
nxtndary = [[0] * (V + 1) for i in range(V + 1)]
for i in range(1, V + 1):
	for j in range(1, V + 1):
		if j == i:
			continue
		found = False
		for z in es[i]:
			k = z[0]
			if dist[i][j] == z[1] + dist[k][j]:
				nxtndary[i][j] = k
				found = True
				break
		if not found:
			print('nxtndary ERR')
			exit()
if prob == 2:
	F = inl()
tt = inn()
pendreq = []
workreq = []
lastnd = 1
distfromlast = 0
for t in range(tt):
	if DBG and t > 3400:
		exit()
	n = inn()
	if n == 1:
		(new_id, dst) = inm()
		pendreq.append((new_id, dst))
	if prob == 2:
		readput()
	if atdepot():
		if trigger():
			setwork()
			if len(workreq) > 0:
				move()
			else:
				stay()
		else:
			stay()
	else:
		move()
	if prob == 2:
		readverd()


import sys
from collections import deque
from heapq import heapify, heappop, heappush

def decide_next_dst(cost, order, t, current_id, store_cost, store_hold, wf):
	d = 0
	c = (t - store_cost) * store_hold * (1000 / wf[current_id][0]) if current_id > 0 else 0
	for key in order:
		if (t - cost[key][0]) * cost[key][1] * (1000 / wf[current_id][key]) >= c:
			d = key
			c = (t - cost[key][0]) * cost[key][1] * (1000 / wf[current_id][key])
	return (d, c)

def solve():
	inf = 10000000000
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	edge = dict()
	wf = dict()
	next_id = dict()
	for i in range(V):
		edge[i] = dict()
		wf[i] = dict()
		next_id[i] = dict()
		for j in range(V):
			edge[i][j] = 0 if i == j else inf
			next_id[i][j] = j
			wf[i][j] = 0 if i == j else inf
	for _ in range(E):
		(u, v, d) = map(int, input().split())
		edge[u - 1][v - 1] = d
		edge[v - 1][u - 1] = d
		wf[u - 1][v - 1] = d
		wf[v - 1][u - 1] = d
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if wf[i][j] > wf[i][k] + wf[k][j]:
					wf[i][j] = wf[i][k] + wf[k][j]
					next_id[i][j] = next_id[i][k]
	T = int(input())
	order = set()
	stuck_order = set()
	command = [None] * T
	heading = 0
	current_id = 0
	dist_left = 0
	final_dist = 0
	stuck_cost = [[0, 0] for _ in range(V)]
	cost = [[0, 0] for _ in range(V)]
	driver_hold = 0
	store_hold = 0
	store_cost = 0
	for t in range(T):
		N = int(input())
		if N == 1:
			(new_id, dst) = map(int, input().split())
			stuck_order |= {dst - 1}
			if stuck_cost[dst - 1][0] == 0:
				stuck_cost[dst - 1][0] = t
			stuck_cost[dst - 1][1] += 1
			store_hold += 1
			if store_cost == 0:
				store_cost = t
		if dist_left > 0:
			command[t] = heading + 1
			dist_left -= 1
		else:
			if heading == 0:
				if store_hold == driver_hold == 0:
					command[t] = -1
					continue
				else:
					order |= stuck_order
					for key in order:
						if cost[key][0] == 0:
							cost[key][0] = stuck_cost[key][0]
						cost[key][1] += stuck_cost[key][1]
						stuck_cost[key] = [0, 0]
					driver_hold += store_hold
					stuck_order = set()
					store_hold = 0
					store_cost = 0
			if heading in order and heading > 0:
				order -= {heading}
				driver_hold -= cost[heading][1]
				cost[heading] = [0, 0]
			current_id = heading
			if len(order) > 0:
				if current_id == final_dist:
					(final_dist, max_hold) = decide_next_dst(cost, order, t, current_id, store_cost, store_hold, wf)
					if driver_hold < store_hold and current_id > 0:
						final_dist = 0
					elif store_hold > 0 and t >= 0.945 * T and (current_id > 0):
						final_dist = 0
			else:
				final_dist = 0
			heading = next_id[current_id][final_dist]
			dist_left = edge[current_id][heading] - 1
			command[t] = heading + 1
	for i in range(T):
		print(command[i])
	return 0
solve()


import sys
from collections import deque
from heapq import heapify, heappop, heappush

def decide_final_dst(cost, order, current_id, store_cost, wf, dav):
	d = 0
	c = (store_cost * (10000 / wf[current_id][0]) if current_id > 0 else 0) * (1 / dav)
	for key in order:
		if cost[key] * (10000 / wf[current_id][key]) > c:
			d = key
			c = cost[key] * (10000 / wf[current_id][key])
	return d

def decide_next_dst(cost, order, current_id, pre_id, heading, edge, wf, passed, V):
	c = cost[heading] * (10000 / wf[current_id][heading])
	if heading in passed or c == 0:
		for e in range(V):
			if e != current_id and wf[current_id][e] < 10000000000:
				if cost[e] * (10000 / wf[current_id][e]) > c:
					heading = e
					c = cost[e] * (10000 / wf[current_id][e])
	return

def solve():
	inf = 10000000000
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	edge = dict()
	wf = dict()
	next_id = dict()
	for i in range(V):
		edge[i] = dict()
		wf[i] = dict()
		next_id[i] = dict()
		for j in range(V):
			edge[i][j] = 0 if i == j else inf
			next_id[i][j] = j
			wf[i][j] = 0 if i == j else inf
	for _ in range(E):
		(u, v, d) = map(int, input().split())
		edge[u - 1][v - 1] = d
		edge[v - 1][u - 1] = d
		wf[u - 1][v - 1] = d
		wf[v - 1][u - 1] = d
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if wf[i][j] > wf[i][k] + wf[k][j]:
					wf[i][j] = wf[i][k] + wf[k][j]
					next_id[i][j] = next_id[i][k]
	daverage = sum(wf[0]) / (V - 1)
	T = int(input())
	order = set()
	stuck_order = set()
	command = [None] * T
	heading = 0
	pre_id = 0
	current_id = 0
	dist_left = 0
	final_dist = 0
	stuck_cost = [0 for _ in range(V)]
	cost = [0 for _ in range(V)]
	driver_hold = 0
	store_hold = 0
	passed = set()
	for t in range(T):
		N = int(input())
		if N == 1:
			(new_id, dst) = map(int, input().split())
			stuck_order |= {dst - 1}
			stuck_cost[dst - 1] += 1
			store_hold += 1
		if dist_left > 0:
			command[t] = heading + 1
			dist_left -= 1
		else:
			if heading == 0:
				passed = set()
				if store_hold == driver_hold == 0:
					command[t] = -1
					continue
				else:
					order |= stuck_order
					for key in order:
						cost[key] += stuck_cost[key]
						driver_hold += stuck_cost[key]
						stuck_cost[key] = 0
					stuck_order = set()
					store_hold = 0
			if heading in order and heading > 0:
				order -= {heading}
				driver_hold -= cost[heading]
				cost[heading] = 0
			pre_id = current_id
			current_id = heading
			passed |= {heading}
			if len(order) > 0:
				if current_id == final_dist:
					final_dist = decide_final_dst(cost, order, current_id, store_hold, wf, daverage)
			else:
				final_dist = 0
			heading = next_id[current_id][final_dist]
			decide_next_dst(cost, order, current_id, pre_id, heading, edge, wf, passed, V)
			dist_left = edge[current_id][heading] - 1
			command[t] = heading + 1
	for i in range(T):
		print(command[i])
	return 0
solve()


(N, M) = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
	(u, v, d) = map(int, input().split())
	X[u - 1].append((v - 1, d))
	X[v - 1].append((u - 1, d))
T = int(input())
t = 0
x = 0
while t < T:
	if t < 5000:
		print(-1)
		t += 1
		continue
	(y, d) = max([(y, d) for (y, d) in X[x]])
	for i in range(d):
		print(y + 1)
		t += 1
		if t >= T:
			break
	x = y


(vertex_number, edge_number) = map(int, input().split())
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 = 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:
			if i == j:
				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):
	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):
	R = []
	if 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
t = 0
t_start = 0
Root = []
while t < T_max - 1:
	Req = []
	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
		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])
for i in range(T_max):
	if i < len(Root):
		print(Root[i])
	else:
		print(-1)


import sys
from collections import deque
from heapq import heapify, heappop, heappush
from math import sqrt

def root_search(order, cost, current_id, wf, V):
	type_num = len(order)
	hold = []
	heapify(hold)
	pre_hold = deque()
	next_search = deque()
	initial = set()
	initial |= order
	pre_hold.append((0, str(current_id), initial, current_id))
	for i in range(type_num):
		while pre_hold:
			(pre_cost, pre_pass, to_search, pre_id) = pre_hold.popleft()
			for key in to_search:
				new_cost = -1 * pre_cost + wf[pre_id][key] / sqrt(cost[key][1])
				new_pass = pre_pass + ' ' + str(key)
				heappush(hold, (-1 * new_cost, new_pass, to_search - {key}, key))
				if len(hold) > 3:
					trush = heappop(hold)
		while hold:
			item = heappop(hold)
			pre_hold.append(item)
	(ans_cost, ans_pass, ans_search, ans_id) = pre_hold.pop()
	pass_list = [int(v) for v in ans_pass.split()]
	pass_list.append(0)
	return pass_list

def decide_next_dst(cost, order, current_id, final_dist, store_cost, wf):
	d = 0
	c = (wf[current_id][0] + wf[0][final_dist]) / sqrt(store_cost)
	if wf[current_id][final_dist] / sqrt(cost[final_dist][1]) > c:
		return 0
	return final_dist

def solve():
	inf = 10000000000
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	edge = dict()
	wf = dict()
	next_id = dict()
	for i in range(V):
		edge[i] = dict()
		wf[i] = dict()
		next_id[i] = dict()
		for j in range(V):
			edge[i][j] = 0 if i == j else inf
			next_id[i][j] = j
			wf[i][j] = 0 if i == j else inf
	for _ in range(E):
		(u, v, d) = map(int, input().split())
		edge[u - 1][v - 1] = d
		edge[v - 1][u - 1] = d
		wf[u - 1][v - 1] = d
		wf[v - 1][u - 1] = d
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if wf[i][j] > wf[i][k] + wf[k][j]:
					wf[i][j] = wf[i][k] + wf[k][j]
					next_id[i][j] = next_id[i][k]
	T = int(input())
	order = set()
	stuck_order = set()
	command = [None] * T
	heading = 0
	dist_left = 0
	final_dist = 0
	driver_hold = 0
	root_pointer = 0
	store_list = [0] * V
	root_list = []
	cost = dict()
	store_time = set()
	for i in range(V):
		cost[i] = [0, 0]
	store_hold = 0
	for t in range(T):
		N = int(input())
		if N == 1:
			(new_id, dst) = map(int, input().split())
			stuck_order |= {dst - 1}
			store_hold += 1
			store_list[dst - 1] += 1
			store_time |= {t}
		if dist_left > 0:
			command[t] = heading + 1
			dist_left -= 1
		else:
			if heading == 0:
				if store_hold == driver_hold == 0:
					command[t] = -1
					continue
				else:
					order |= stuck_order
					driver_hold += store_hold
					for key in order:
						cost[key][1] += (E - V) / V * cost[key][0] + store_list[key]
						cost[key][0] += store_list[key]
						store_list[key] = 0
					stuck_order = set()
					store_time = set()
					store_hold = 0
					root_list = root_search(order, cost, 0, wf, V)
					current_id = heading = final_dist = 0
					root_pointer = 0
			if heading in order:
				order -= {heading}
				driver_hold -= cost[heading][0]
				cost[heading] = [0, 0]
			current_id = heading
			if current_id == final_dist:
				final_dist = root_list[root_pointer + 1]
				root_pointer += 1
				if current_id > 0 and cost[final_dist][1] > 0 and (store_hold > 0):
					final_dist = decide_next_dst(cost, order, current_id, final_dist, store_hold, wf)
			heading = next_id[current_id][final_dist]
			dist_left = edge[current_id][heading] - 1
			command[t] = heading + 1
	for i in range(T):
		print(command[i])
	return 0
solve()


import time
st_time = time.time()
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import random

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
ts = time.time()
sys.setrecursionlimit(10 ** 6)
show_flg = False
prob = 'A'
drop_probability = 1

def dijkstra(edge, st):
	n = len(edge)
	d = [(0 if st == i else inf, i) for i in range(n)]
	prev = [0] * n
	q = [i for i in d]
	heapify(q)
	while q:
		(dist, cur) = heappop(q)
		for (dst, dist) in edge[cur]:
			alt = d[cur][0] + dist
			if alt < d[dst][0]:
				d[dst] = (alt, dst)
				prev[dst] = cur
				heappush(q, (alt, dst))
	dist = [i for (i, j) in d]
	return (dist, prev)
(V, E) = MI()
g = [[] for _ in range(V + 1)]
c = []
neighber = [set() for _ in range(V + 1)]
d_map = [{} for _ in range(V + 1)]
for i in range(E):
	(u, v, d) = MI()
	g[u].append((v, d))
	g[v].append((u, d))
	c.append((u, v, d))
	neighber[u].add(v)
	neighber[v].add(u)
	d_map[u][v] = d
	d_map[v][u] = d
for i in sorted(c):
	0
mins = [[] for _ in range(V + 1)]
prevs = [[] for _ in range(V + 1)]
for i in range(1, V + 1):
	(min_dist, prev) = dijkstra(g, i)
	mins[i] = min_dist
	prevs[i] = prev
if prob == 'B':
	f = LI()
T = I()
order = [0] * T
accor = [0] * T
order_time = []
order_at_shop = []
item_at_car = [[] for _ in range(V + 1)]
num_item_at_car = 0

def ship():
	global num_item_at_car
	while order_at_shop:
		(v, t) = order_at_shop.pop()
		item_at_car[v].append(t)
		num_item_at_car += 1
	show('item_at_car', item_at_car)

def deliver(v, deliver_t):
	global num_item_at_car
	d_p = 0
	while item_at_car[v]:
		or_t = item_at_car[v].pop()
		num_item_at_car -= 1
		d_p += T ** 2 - (deliver_t - or_t) ** 2
	show('delivered to', v, 'deliverPoint', d_p)
	return d_p

def stat_init():
	global order_at_shop
	global item_at_car
	global num_item_at_car
	order_at_shop = []
	item_at_car = [[] for _ in range(V + 1)]
	num_item_at_car = 0

def root_valuator(current, now, root, f_info=True):
	if len(root) == 0:
		return (0, 0)
	global item_at_car
	cur = current
	point = 0
	rt = now
	for (next_dest, dist) in root[::-1]:
		if len(item_at_car[next_dest]) > 0:
			rt += dist
			for j in item_at_car[next_dest]:
				point += T ** 2 - (rt - j) ** 2
		cur = next_dest
	return (point, rt - now)

def neighber_search(cur, next_dest, effc, best_p, best_d, f_info=True):
	global item_at_car
	drop = []
	n_item = 0
	for (nb, dist) in g[cur]:
		if nb == next_dest:
			continue
		if len(item_at_car[nb]) > n_item:
			n_item = len(item_at_car[nb])
			drop_effc = (best_p + n_item * T ** 2) / (mins[cur][nb] * 2 + best_d)
			if drop_effc >= effc:
				drop = [(cur, mins[nb][cur]), (nb, mins[cur][nb])]
	return drop

def optimizer_drop(current, now, root, effc, best_p, best_d, f_info=True):
	show('!Optimizing', root)
	global item_at_car
	opt_root = []
	cur = current
	org_now = now
	org_effc = effc
	n = len(root)
	for i in range(1, n + 1):
		(next_dest, dist) = root[-i]
		drop = []
		alt = 0
		n_item = 0
		for (nb, d_nb) in g[cur]:
			if nb == next_dest:
				continue
			if len(item_at_car[nb]) > n_item:
				rt = now + d_nb
				for j in item_at_car[nb]:
					alt += T ** 2 - (rt - j) ** 2
				if prevs[nb][next_dest] == nb:
					drop_time = mins[cur][nb] + mins[nb][next_dest] - dist
					drop_effc = (best_p + alt) / (drop_time + best_d)
					if drop_effc >= effc:
						effc = drop_effc
						drop.append((nb, mins[cur][nb]))
						drop.append((next_dest, mins[nb][next_dest]))
				elif 0 == 1:
					drop_time = mins[cur][nb] * 2
					drop_effc = (best_p + alt) / (drop_time + best_d)
					if drop_effc >= effc:
						effc = drop_effc
						drop.append((nb, mins[cur][nb]))
						drop.append((cur, mins[nb][cur]))
						drop.append((next_dest, mins[cur][next_dest]))
		if drop:
			opt_root += drop
			now += drop_time
			show('#yorimichi', drop)
		else:
			opt_root.append((next_dest, dist))
			now += dist
		cur = next_dest
	opt_valid = True
	cur = current
	for (next_dest, dist) in opt_root:
		if next_dest in neighber[cur]:
			if d_map[cur][next_dest] != dist:
				opt_valid = False
			else:
				0
		else:
			opt_valid = False
		cur = next_dest
	if opt_valid:
		(p, t) = root_valuator(current, org_now, opt_root, f_info=False)
		opt_effc = p / t if t != 0 else 0
		if org_effc <= opt_effc:
			rt = opt_root[::-1]
		else:
			rt = root
	else:
		show('!!optimization failed')
		rt = root
	return rt

def best_deliver(cur, now, f_info=True):
	show('best_del called')
	global order_at_shop
	global item_at_car
	global num_item_at_car
	effc = 0
	(best_p, best_d) = (0, inf)
	deliver_point = 1
	for dest in range(2, V + 1):
		if dest == cur:
			continue
		d = mins[cur][dest]
		rt = now + d
		alt = 0
		for j in item_at_car[dest]:
			alt += T ** 2 - (rt - j) ** 2
		if alt / d > effc:
			(effc, best_p, best_d) = (alt / d, alt, d)
			deliver_point = dest
	if cur != 1:
		db = mins[cur][1]
		nx_item_at_car = [[] for i in range(1 + V)]
		for (order_v, t) in order_at_shop:
			nx_item_at_car[order_v].append(t)
		for i in range(2, 1 + V):
			for t in item_at_car[i]:
				nx_item_at_car[i].append(t)
		if f_info:
			for t in range(min(now + 1, T - 1), min(now + db + 1, T)):
				v = order[t]
				if v != 0:
					nx_item_at_car[v].append(t)
		for dest in range(2, V + 1):
			if cur == 1:
				break
			if dest == cur:
				continue
			dg = mins[1][dest]
			rt = now + db + dg
			d = db + dg
			alt = 0
			for j in nx_item_at_car[dest]:
				alt += T ** 2 - (rt - j) ** 2
			if alt / d > effc:
				(effc, best_p, best_d) = (alt / d, alt, d)
				deliver_point = 1
	root = []
	p = deliver_point
	while p != cur:
		prev_p = prevs[cur][p]
		root.append((p, mins[p][prev_p]))
		p = prev_p
	if deliver_point == 1:
		0
	else:
		root = optimizer_drop(cur, now, root, effc, best_p, best_d, f_info=True)
	show('best_del return', deliver_point, root, effc)
	return (deliver_point, root, effc)

def solve_A(wait_num):
	stat_init()
	move = []
	state = 0
	reached = False
	final_dest = 1
	dest = 1
	cur = 1
	point = 0
	effc = 0
	for t in range(T):
		Nnew = I()
		for j in range(Nnew):
			(new_id, v) = MI()
			order[t] = v
	for t in range(T):
		show(t, cur, state)
		v = order[t]
		if v != 0:
			order_at_shop.append((v, t))
		if cur == 1 and state == 0:
			ship()
		if num_item_at_car <= wait_num and cur == 1 and (state == 0):
			print(-1)
			sys.stdout.flush()
			ship()
		else:
			if state == 0:
				if dest == 1:
					ship()
				else:
					point += deliver(dest, t)
				if cur == final_dest:
					(final_dest, root, effc) = best_deliver(cur, t, f_info=True)
					show('root setting', final_dest, root)
				else:
					0
				if len(root) == 0:
					print(-1)
					sys.stdout.flush()
					continue
				(dest, dist) = root.pop()
				state = 1
			else:
				0
			print(dest)
			sys.stdout.flush()
			dist -= 1
			show('moving to', dest, 'root', root)
			if dist == 0:
				state = 0
				cur = dest
	return point
mode = 'rand'
mode = 'greed'
mode = 'greed_A'
if mode == 'rand':
	time_limit = 29.5
	time_limit = 0.07
	now = time.time()
	p = -1
	s = T // 2
	c = 1
	while True:
		c += 1
		now = time.time()
		if now - st_time > time_limit:
			break
		(cur_p, cur_st, cur_move) = rand_move(s, c)
		if cur_p > p or p == -1:
			p = cur_p
			s = cur_st
			move = cur_move
elif mode == 'greed':
	point = interactive(wait_num=3)
elif mode == 'greed_A':
	point = solve_A(wait_num=0)


import copy

def deleteProduct(nowPos):
	for i in range(len(product)):
		if nowPos == product[i][2]:
			del product[i]
			break

def getDistance(x, y):
	global route
	NODE_ROUTE = 0
	NODE_DEFINED = 1
	NODE_COST = 2
	NODE_CHG_FROM = 3
	distance = 100
	temp_node = [[] for i in range(V)]
	for i in range(V):
		temp_node[i].append(copy.deepcopy(es[i]))
		temp_node[i].append(0)
		temp_node[i].append(-1)
		temp_node[i].append(0)
	temp_node[y][NODE_COST] = 0
	while 1:
		for i in range(V):
			if temp_node[i][NODE_DEFINED] == 1 or temp_node[i][NODE_COST] < 0:
				continue
			else:
				break
		loop_end_flag = 1
		for k in range(len(temp_node)):
			if temp_node[k][NODE_DEFINED] == 0:
				loop_end_flag = 0
		if loop_end_flag == 1:
			break
		temp_node[i][NODE_DEFINED] = 1
		temp_node_to = 0
		temp_node_cost = 0
		for j in range(len(temp_node[i][NODE_ROUTE])):
			temp_node_to = temp_node[i][NODE_ROUTE][j][0]
			temp_node_cost = temp_node[i][NODE_COST] + temp_node[i][NODE_ROUTE][j][1]
			if temp_node[temp_node_to][NODE_COST] < 0:
				temp_node[temp_node_to][NODE_COST] = temp_node_cost
				temp_node[temp_node_to][NODE_CHG_FROM] = i
			elif temp_node[temp_node_to][NODE_COST] > temp_node_cost:
				temp_node[temp_node_to][NODE_COST] = temp_node_cost
				temp_node[temp_node_to][NODE_CHG_FROM] = i
	cost = 0
	route_num = 0
	i = x
	route.clear()
	while 1:
		cost = cost + temp_node[i][NODE_COST]
		if y == i:
			distande = cost
			break
		moto_node = i
		i = temp_node[i][NODE_CHG_FROM]
		route.append([i, 0])
		for j in range(len(temp_node[moto_node][0])):
			if temp_node[moto_node][0][j][0] == route[route_num][0]:
				route[route_num][1] = temp_node[moto_node][0][j][1]
		route_num = route_num + 1
	return distance
route = []

def getTargetPos(now_pos):
	global product
	global pos
	global route
	pos = product[0][2]
	return pos
product = []

def getProduct(currentTime):
	for i in range(len(order)):
		if order[i][0] == currentTime:
			product.append(copy.deepcopy(order[i]))

def gotoVertex(x, y):
	global nowPos
	global route
	global total_move_count
	i = 0
	while 1:
		if x == y:
			print(-1)
			total_move_count = total_move_count + 1
			if total_move_count >= T:
				return
			break
		if route[i][0] == y:
			for j in range(route[i][1]):
				print(route[i][0] + 1)
				total_move_count = total_move_count + 1
				if total_move_count >= T:
					return
			break
		else:
			for j in range(route[i][1]):
				print(route[i][0] + 1)
				total_move_count = total_move_count + 1
				if total_move_count >= T:
					return
		i = i + 1
	nowPos = y
(V, E) = map(int, input().split())
es = [[] for i in range(V)]
for i in range(E):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	es[a].append([b, c])
	es[b].append([a, c])
T = int(input())
order = []
total_move_count = 0
for i in range(T):
	Nnew = int(input())
	for j in range(Nnew):
		(new_id, dst) = map(int, input().split())
		order.append([Nnew, new_id, dst - 1, 0])
nowPos = 0
targetPos = -1
for i in range(T):
	if nowPos == 0:
		getProduct(i + 1)
		if len(product) == 0:
			while 1:
				gotoVertex(nowPos, 0)
				print(-1)
				if total_move_count >= T:
					break
	if len(product) != 0:
		targetPos = getTargetPos(nowPos)
		getDistance(nowPos, targetPos)
		gotoVertex(nowPos, targetPos)
	if nowPos == targetPos:
		deleteProduct(nowPos)
	if len(product) == 0:
		getDistance(nowPos, 0)
		gotoVertex(nowPos, 0)
	if total_move_count >= T:
		break


from collections import defaultdict
import random
from logging import getLogger, StreamHandler, DEBUG, ERROR
from functools import lru_cache
logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(ERROR)
logger.addHandler(handler)
logger.propagate = False
logger.debug('HEADER')

class Maps(object):

	def __init__(self):
		self.readinputs()

	def readinputs(self):
		(self.V, self.E) = map(int, input().split())
		self.es = [[] for i in range(self.V)]
		self.Mes = [[0] * self.V for i in range(self.V)]
		self.graph = Graph()
		self.car = Car()
		self.here = ('v', 0)
		self.plan = []
		for _ in range(self.E):
			(a, b, c) = map(int, input().split())
			(a, b) = (a - 1, b - 1)
			self.es[a].append((b, c))
			self.es[b].append((a, c))
			self.Mes[a][b] = c
			self.Mes[b][a] = c
			self.graph.add_edge(a, b, c)
		self.T = int(input())
		self.info = [[] for i in range(self.T)]
		for t in range(self.T):
			Nnew = int(input())
			for _ in range(Nnew):
				(new_id, dst) = map(int, input().split())
				dst = dst - 1
				self.info[t].append((new_id, dst))
		logger.debug('Set status')
		logger.debug('Info :')
		logger.debug(self.info)

	def get_plan(self):
		return self.plan

	def has_plan(self):
		if self.plan == []:
			return False
		else:
			return True

	def get_here(self):
		return self.here

	def set_here(self, here):
		self.here = here

	def next_place(self, here, command):
		if command == -2:
			return here
		else:
			to = command
			if here[0] == 'v':
				dist = self.Mes[here[1]][to]
				if dist == 0:
					raise ValueError('Dist has not 0')
				elif dist == 1:
					return ('v', to)
				else:
					return ('e', here[1], to, 1)
			elif here[0] == 'e':
				if here[2] == to:
					if here[3] + 1 < self.Mes[here[1]][here[2]]:
						return ('e', here[1], here[2], here[3] + 1)
					elif here[3] + 1 == self.Mes[here[1]][here[2]]:
						return ('v', here[2])
					else:
						raise ValueError('Distance error!')
				elif here[1] == to:
					if here[3] - 1 > 0:
						return ('e', here[1], here[2], here[3] - 1)
					elif here[3] - 1 == 0:
						return ('v', here[1])
					else:
						raise ValueError('Distance error!')
			else:
				raise ValueError('Here has vertex or edge status')

	def get_command(self, here, plan):
		if here[0] == 'v':
			if plan == []:
				return -2
			elif here[1] == plan[-1]:
				return -2
			else:
				return plan[plan.index(here[1]) + 1]
		elif here[0] == 'e':
			return here[2]
		else:
			raise ValueError('Here has vertex or edge status')

	def move(self):
		where = [('v', 0)]
		dist_time = 0
		self.path = [0] * self.T
		last_stay_0 = 0
		for t in range(self.T):
			now_where = where[-1]
			logger.debug('----------Time----------')
			logger.debug(t)
			logger.debug('Here is  :')
			logger.debug(now_where)
			logger.debug('parcel  :')
			logger.debug(self.info[t])
			if now_where[0] == 'v':
				if now_where[1] == 0:
					logger.debug('Car Parameter :')
					logger.debug('Last stay at 0 :')
					logger.debug(last_stay_0)
					logger.debug('Picking up parcel is :')
					for parcel in self.info[last_stay_0:t + 1]:
						logger.debug(parcel)
						self.car.pickup(parcel)
					last_stay_0 = t + 1
				else:
					self.car.unload(now_where[1])
			logger.debug('Car Box  :')
			logger.debug(self.car.box)
			if self.car.box == []:
				logger.debug('Car Box is vacant')
				if now_where[0] == 'v' and now_where[1] == 0:
					self.path[t] = -2
					where.append(('v', 0))
					logger.debug('Time ' + str(t) + ' command is :')
					logger.debug(self.path[t])
					logger.debug('No parcel and stay at 1. Continue')
					continue
			if not self.has_plan():
				logger.debug('--Set plan--')
				logger.debug('-Now-')
				logger.debug(now_where)
				logger.debug('-Dests-')
				logger.debug(self.car.show_dest())
				if now_where[1] != 0:
					goal = 0
					dist_time += 1
				else:
					goal = self.select_goal(now_where[1], self.car.show_dest())
					dist_time += 1
				logger.debug('Set Goal is :')
				logger.debug(goal)
				self.plan = wrap_dijsktra(self.graph, now_where[1], goal)
			logger.debug('Time ' + str(t) + ' plan is :')
			logger.debug(self.plan)
			if self.plan == []:
				logger.debug('Time ' + str(t) + ' has no plan')
				self.path[t] = -2
				continue
			command = self.get_command(now_where, self.plan)
			self.path[t] = command
			logger.debug('Time ' + str(t) + ' command is :')
			logger.debug(command)
			where.append(self.next_place(now_where, command))
			logger.debug('Time ' + str(t) + ' next place is :')
			logger.debug(where[-1])
			if where[-1][0] == 'v' and where[-1][1] == self.plan[-1]:
				logger.debug('Time ' + str(t) + ' we arrive at goal !')
				self.plan = []

	def select_goal(self, here, dests):
		dist = dict()
		for dest in dests:
			path = wrap_dijsktra(self.graph, here, dest)
			dist[dest] = self.dist_path(path)
		nearby = min(dist, key=dist.get)
		return nearby

	def dist_path(self, path):
		distance = 0
		for n in range(len(path) - 1):
			distance += self.Mes[path[n]][path[n + 1]]
		return distance

	def output(self):
		for t in range(self.T):
			print(self.path[t] + 1)

class Graph:

	def __init__(self):
		self.edges = defaultdict(list)
		self.weights = {}

	def add_edge(self, from_node, to_node, weight):
		self.edges[from_node].append(to_node)
		self.edges[to_node].append(from_node)
		self.weights[from_node, to_node] = weight
		self.weights[to_node, from_node] = weight

class Car(object):

	def __init__(self):
		self.box = []

	def pickup(self, parcel):
		if parcel == []:
			pass
		else:
			self.box.append(parcel[0])

	def unload(self, vertex):
		self.box = [x for x in self.box if x[1] != vertex]

	def show_dest(self):
		dest = set()
		for x in self.box:
			dest.add(x[1])
		if len(dest) == 0:
			dest.add(0)
		return list(dest)

def wrap_dijsktra(graph, initial, end):
	if initial == end:
		return []
	elif initial < end:
		return dijsktra(graph, initial, end)
	else:
		return dijsktra(graph, end, initial)[::-1]

@lru_cache(maxsize=80000)
def dijsktra(graph, initial, end):
	shortest_paths = {initial: (None, 0)}
	current_node = initial
	visited = set()
	while current_node != end:
		visited.add(current_node)
		destinations = graph.edges[current_node]
		weight_to_current_node = shortest_paths[current_node][1]
		for next_node in destinations:
			weight = graph.weights[current_node, next_node] + weight_to_current_node
			if next_node not in shortest_paths:
				shortest_paths[next_node] = (current_node, weight)
			else:
				current_shortest_weight = shortest_paths[next_node][1]
				if current_shortest_weight > weight:
					shortest_paths[next_node] = (current_node, weight)
		next_destinations = {node: shortest_paths[node] for node in shortest_paths if node not in visited}
		if not next_destinations:
			return 'Route Not Possible'
		current_node = min(next_destinations, key=lambda k: next_destinations[k][1])
	path = []
	while current_node is not None:
		path.append(current_node)
		next_node = shortest_paths[current_node][0]
		current_node = next_node
	path = path[::-1]
	return path

def main():
	M = Maps()
	M.move()
	M.output()
main()


(V, E) = map(int, input().split())
for i in range(E):
	input()
T = int(input())
for i in range(T):
	print(-1)


from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
input = stdin.readline
(V, E) = map(int, input().split())
graph = [[0] * V for _ in range(V)]
for _ in range(E):
	(u, v, d) = map(int, input().split())
	(u, v) = (u - 1, v - 1)
	graph[u][v] = graph[v][u] = d
now = 1
T_max = int(input().rstrip())
for _ in range(T_max):
	N_max = int(input().rstrip())
	for _ in range(N_max):
		(new_id, dst) = map(int, input().split())
	print(-1)


[print(-1) for i in range(10000)]


import sys
from random import randint
from copy import deepcopy
from collections import deque
from heapq import heapify, heappop, heappush

def salesman(cost, order, wf):
	vo = [0]
	left = set()
	left |= order
	now_id = 0
	while left:
		min_cost = 10000000
		dist = 0
		for key in left:
			if wf[now_id][key] < min_cost:
				min_cost = wf[now_id][key]
				dist = key
		left -= {dist}
		vo.append(dist)
		now_id = dist
	vo.append(0)
	order_num = len(order)
	for _ in range(order_num ** 2):
		(a, b) = (randint(0, order_num), randint(0, order_num))
		if a == b:
			continue
		(a, b) = (min(a, b), max(a, b))
		d_cost = wf[vo[a]][vo[b]] + wf[vo[a + 1]][vo[b + 1]]
		d_cost -= wf[vo[a]][vo[a + 1]] + wf[vo[b]][vo[b + 1]]
		if d_cost < 0:
			swap = deepcopy(vo[a + 1:b + 1])
			for i in range(b - a):
				vo[a + 1 + i] = swap[b - a - 1 - i]
	return vo

def solve():
	inf = 10000000000
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	edge = dict()
	wf = dict()
	next_id = dict()
	for i in range(V):
		edge[i] = dict()
		wf[i] = dict()
		next_id[i] = dict()
		for j in range(V):
			edge[i][j] = 0 if i == j else inf
			next_id[i][j] = j
			wf[i][j] = 0 if i == j else inf
	for _ in range(E):
		(u, v, d) = map(int, input().split())
		edge[u - 1][v - 1] = d
		edge[v - 1][u - 1] = d
		wf[u - 1][v - 1] = d
		wf[v - 1][u - 1] = d
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if wf[i][j] > wf[i][k] + wf[k][j]:
					wf[i][j] = wf[i][k] + wf[k][j]
					next_id[i][j] = next_id[i][k]
	T = int(input())
	order = set()
	stuck_order = set()
	command = [None] * T
	current_id = 0
	final_dist = 0
	heading = 0
	dist_left = 0
	stuck_cost = [0 for _ in range(V)]
	cost = [0 for _ in range(V)]
	driver_hold = 0
	store_hold = 0
	order_id = 0
	visit_order = []
	for t in range(T):
		N = int(input())
		if N == 1:
			(new_id, dst) = map(int, input().split())
			stuck_order |= {dst - 1}
			stuck_cost[dst - 1] += 1
			store_hold += 1
		if dist_left > 0:
			dist_left -= 1
			command[t] = heading + 1
		else:
			if heading == 0:
				if store_hold == driver_hold == 0:
					command[t] = -1
					continue
				else:
					for key in stuck_order:
						cost[key] += stuck_cost[key]
						driver_hold += stuck_cost[key]
						stuck_cost[key] = 0
					order |= stuck_order
					stuck_order = set()
					store_hold = 0
					visit_order = salesman(cost, order, wf)
					order_id = 0
				current_id = final_dist = 0
			elif heading in order:
				driver_hold -= cost[heading]
				cost[heading] = 0
				order -= {heading}
			current_id = heading
			if current_id == final_dist:
				final_dist = visit_order[order_id + 1]
				order_id += 1
			heading = next_id[current_id][final_dist]
			dist_left = edge[current_id][heading] - 1
			command[t] = heading + 1
	for i in range(T):
		print(command[i])
	return 0
solve()


import copy

def deleteProduct(nowPos):
	global product
	for i in reversed(range(len(product))):
		if nowPos == product[i][2]:
			del product[i]
NODE_ROUTE = 0
NODE_DEFINED = 1
NODE_COST = 2
NODE_CHG_FROM = 3

def getDistance(x, y):
	global route
	global temp_node
	temp_node.clear()
	temp_node = [[] for i in range(V)]
	distance = 100
	for i in range(V):
		temp_node[i].append(copy.deepcopy(es[i]))
		temp_node[i].append(0)
		temp_node[i].append(-1)
		temp_node[i].append(0)
	temp_node[y][NODE_COST] = 0
	while 1:
		for i in range(V):
			if temp_node[i][NODE_DEFINED] == 1 or temp_node[i][NODE_COST] < 0:
				continue
			else:
				break
		loop_end_flag = 1
		for k in range(len(temp_node)):
			if temp_node[k][NODE_DEFINED] == 0:
				loop_end_flag = 0
		if loop_end_flag == 1:
			break
		temp_node[i][NODE_DEFINED] = 1
		temp_node_to = 0
		temp_node_cost = 0
		for j in range(len(temp_node[i][NODE_ROUTE])):
			temp_node_to = temp_node[i][NODE_ROUTE][j][0]
			temp_node_cost = temp_node[i][NODE_COST] + temp_node[i][NODE_ROUTE][j][1]
			if temp_node[temp_node_to][NODE_COST] < 0:
				temp_node[temp_node_to][NODE_COST] = temp_node_cost
				temp_node[temp_node_to][NODE_CHG_FROM] = i
			elif temp_node[temp_node_to][NODE_COST] > temp_node_cost:
				temp_node[temp_node_to][NODE_COST] = temp_node_cost
				temp_node[temp_node_to][NODE_CHG_FROM] = i
			if temp_node_to == y:
				loop_end_flag = 1
	distance = decide_route(x, y)
	return distance

def decide_route(x, y):
	cost = 0
	route_num = 0
	i = x
	route.clear()
	distance = 0
	while 1:
		cost = cost + temp_node[i][NODE_COST]
		if y == i:
			distande = cost
			break
		moto_node = i
		i = temp_node[i][NODE_CHG_FROM]
		route.append([i, 0])
		for j in range(len(temp_node[moto_node][0])):
			if temp_node[moto_node][0][j][0] == route[route_num][0]:
				route[route_num][1] = temp_node[moto_node][0][j][1]
		distance = distance + route[route_num][1]
		route_num = route_num + 1
	return distance
route = []

def getTargetPos(now_pos):
	global product
	global pos
	global route
	global prePos
	count = 0
	for i in range(len(order)):
		if time_step_before < order[i][0] <= time_step:
			count = count + 1
	if count > len(product) / 2:
		pos = 0
	else:
		pos = product[-1][2]
	return pos
product = []

def getProduct(currentTime):
	for i in range(len(order)):
		if time_step_before < order[i][0] <= currentTime:
			product.append(copy.deepcopy(order[i]))
prePos = 0

def gotoVertex(x, y):
	global nowPos
	global route
	global total_move_count
	prePos = nowPos
	nowPos = -1
	print(route[0][0] + 1)
	route[0][1] = route[0][1] - 1
	if route[0][1] == 0:
		deleteProduct(route[0][0])
		nowPos = route[0][0]
		del route[0]

def selectWait():
	global wait_cost
	global go_cost
	global result_cost
	for i in range(len(order)):
		if time_step < order[i][0]:
			wait_cost = order[i][0] - time_step
			break
	if len(product) <= 2:
		go_cost = getDistance(nowPos, product[0][2])
	if wait_cost - go_cost > 0:
		result_cost = wait_cost - go_cost
	else:
		result_cost = go_cost - wait_cost
	if len(product) > 50:
		return 0
	elif wait_cost <= 10:
		return 1
	else:
		return 0

def initProduct(nowPos):
	global temp_node
	global product
	getDistance(nowPos, product[0][2])
	for i in range(len(product)):
		for j in range(len(temp_node)):
			if product[i][2] == j:
				product[i][3] = temp_node[j][2]
	product = sorted(product, key=lambda x: x[3])
(V, E) = map(int, input().split())
es = [[] for i in range(V)]
for i in range(E):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	es[a].append([b, c])
	es[b].append([a, c])
T = int(input())
order = []
temp_node = [[] for i in range(V)]
total_move_count = 0
for i in range(T):
	Nnew = int(input())
	for j in range(Nnew):
		(new_id, dst) = map(int, input().split())
		order.append([i, new_id, dst - 1, 0])
nowPos = 0
targetPos = -1
time_step = 0
time_step_before = 0
for i in range(T):
	if time_step >= T:
		break
	if nowPos == 0:
		getProduct(time_step)
		time_step_before = time_step
		if len(product) != 0:
			if selectWait() == 1:
				print(-1)
				time_step = time_step + 1
				total_move_count = total_move_count + 1
				if time_step >= T:
					break
				continue
			else:
				time_step = time_step
				initProduct(nowPos)
		else:
			print(-1)
			time_step = time_step + 1
			total_move_count = total_move_count + 1
			if time_step >= T:
				break
			continue
	if len(product) != 0:
		targetPos = getTargetPos(nowPos)
		if len(route) == 0:
			getDistance(nowPos, targetPos)
		gotoVertex(nowPos, targetPos)
		time_step = time_step + 1
		continue
	if len(product) == 0 and nowPos != 0:
		if len(route) == 0:
			getDistance(nowPos, 0)
		gotoVertex(nowPos, 0)
		time_step = time_step + 1
		continue


from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
import random

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
ts = time.time()
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
show_flg = False
(V, E) = MI()
g = [[] for _ in range(V + 1)]
for i in range(E):
	(u, v, d) = MI()
	g[u].append((v, d))
	g[v].append((u, d))
T = I()
order = [0] * T
accor = [0] * T
for i in range(T):
	n = I()
	accor[i] = accor[i - 1]
	if n > 0:
		(oid, v) = MI()
		order[i] = v
		accor[i] += 1

def rand_move():
	move = []
	state = 0
	cur = 1
	st = min(T // 2, bisect.bisect(accor, V // 4))
	for t in range(st):
		print(-1)
	for t in range(st, T):
		if state == 0:
			r = len(g[cur])
			(dest, dist) = g[cur][random.randint(0, r - 1)]
			state = 1
			move.append(dest)
			dist -= 1
			if dist == 0:
				state = 0
				cur = dest
		else:
			move.append(dest)
			dist -= 1
			if dist == 0:
				state = 0
				cur = dest
	return move
for i in range(1, V + 1):
	show(i, g[i])
move = rand_move()
for i in move:
	print(i)


def get_orders(order_time):
	n_new_order = int(input())
	orders = []
	for _ in range(n_new_order):
		(order_id, destination) = map(int, input().split())
		orders.append((order_id, order_time, destination))
	return orders

def get_input():
	(n_vertices, n_edges) = map(int, input().split())
	graph = [[] for i in range(n_vertices + 1)]
	for _ in range(n_edges):
		(u, v, d) = map(int, input().split())
		graph[u].append((v, d))
		graph[v].append((u, d))
	time_max = int(input())
	orders = []
	for time_index in range(time_max):
		new_orders = get_orders(time_index)
		for order in new_orders:
			orders.append(order)
	return (n_vertices, n_edges, graph, time_max, orders)

def main():
	(n_vertices, n_edges, graph, time_max, orders) = get_input()
	for i in range(time_max):
		print(-1)
main()


import random

class maps(object):

	def __init__(self):
		self.readinputs()

	def readinputs(self):
		(self.V, self.E) = map(int, input().split())
		self.es = [[] for i in range(self.V)]
		self.Mes = [[0] * self.V for i in range(self.V)]
		for _ in range(self.E):
			(a, b, c) = map(int, input().split())
			(a, b) = (a - 1, b - 1)
			self.es[a].append((b, c))
			self.es[b].append((a, c))
			self.Mes[a][b] = c
			self.Mes[b][a] = c
		self.T = int(input())
		self.info = [[] for i in range(self.T)]
		for t in range(self.T):
			Nnew = int(input())
			for _ in range(Nnew):
				(new_id, dst) = map(int, input().split())
				self.info[t].append((new_id, dst))

	def random_walk(self):
		where = [('v', 0)]
		self.path = [0] * self.T
		for t in range(self.T):
			now_where = where[-1]
			if now_where[0] == 'v':
				(to, dist) = random.choice(self.es[now_where[1]])
				self.path[t] = to
				if dist == 1:
					where.append(('v', to))
				else:
					where.append(('e', now_where[1], to, 1))
			elif now_where[0] == 'e':
				now_where = where[-1]
				if True:
					self.path[t] = now_where[2]
					if now_where[3] + 1 < self.Mes[now_where[1]][now_where[2]]:
						where.append(('e', now_where[1], now_where[2], now_where[3] + 1))
					elif now_where[3] + 1 == self.Mes[now_where[1]][now_where[2]]:
						where.append(('v', now_where[2]))
					else:
						pass
				else:
					self.path[t] = now_where[1]
					if now_where[3] - 1 > 0:
						where.append(('e', now_where[1], now_where[2], now_where[3] - 1))
					elif now_where[3] - 1 == 0:
						where.append(('v', now_where[1]))
					else:
						pass
			else:
				pass

	def output(self):
		for t in range(self.T):
			print(self.path[t] + 1)
M = maps()
M.random_walk()
M.output()


import sys
from collections import deque
from heapq import heapify, heappop, heappush

def decide_next_dst(cost, order, current_id, wf):
	d = 0
	c = 0
	for key in order:
		if cost[key][0] * (10000 / wf[current_id][key]) > c:
			d = key
			c = cost[key][0] * (10000 / wf[current_id][key])
	return (d, c)

def solve():
	inf = 10000000000
	input = sys.stdin.readline
	(V, E) = map(int, input().split())
	edge = dict()
	wf = dict()
	next_id = dict()
	for i in range(V):
		edge[i] = dict()
		wf[i] = dict()
		next_id[i] = dict()
		for j in range(V):
			edge[i][j] = 0 if i == j else inf
			next_id[i][j] = j
			wf[i][j] = 0 if i == j else inf
	for _ in range(E):
		(u, v, d) = map(int, input().split())
		edge[u - 1][v - 1] = d
		edge[v - 1][u - 1] = d
		wf[u - 1][v - 1] = d
		wf[v - 1][u - 1] = d
	for k in range(V):
		for i in range(V):
			for j in range(V):
				if wf[i][j] > wf[i][k] + wf[k][j]:
					wf[i][j] = wf[i][k] + wf[k][j]
					next_id[i][j] = next_id[i][k]
	T = int(input())
	order = set()
	stuck_order = set()
	command = [None] * T
	heading = 0
	dist_left = 0
	final_dist = 0
	stuck_cost = [[0, 0] for _ in range(V)]
	cost = [[0, 0] for _ in range(V)]
	driver_hold = 0
	store_hold = 0
	total_order = [0] * (T + 1)
	dt = [0] * T
	Tpeak = (0 + 0.95 * T) / 2
	peak_passed = False
	for t in range(T):
		N = int(input())
		total_order[t + 1] = total_order[t] + N
		dt[t] = total_order[t + 1] / 500 if t < 498 else (total_order[t + 1] - total_order[t - 498]) / 500
		if not peak_passed and dt[t] >= 0.6:
			peak_passed = True
		elif not peak_passed:
			Tpeak = (t + 0.95 * T) / 2
		if N == 1:
			(new_id, dst) = map(int, input().split())
			stuck_order |= {dst - 1}
			stuck_cost[dst - 1][0] += Tpeak - t if not peak_passed else t
			stuck_cost[dst - 1][1] += 1
			store_hold += 1
		if dist_left > 0:
			command[t] = heading + 1
			dist_left -= 1
		else:
			if heading == 0:
				if store_hold == driver_hold == 0:
					command[t] = -1
					continue
				else:
					order |= stuck_order
					for key in order:
						cost[key][0] += stuck_cost[key][0]
						cost[key][1] += stuck_cost[key][1]
						driver_hold += stuck_cost[key][1]
						stuck_cost[key] = [0, 0]
					stuck_order = set()
					store_hold = 0
			if heading in order and heading > 0:
				order -= {heading}
				driver_hold -= cost[heading][1]
				cost[heading] = [0, 0]
			current_id = heading
			if len(order) > 0:
				if current_id == final_dist:
					(final_dist, max_hold) = decide_next_dst(cost, order, current_id, wf)
					if driver_hold < store_hold and current_id > 0:
						final_dist = 0
					elif store_hold > 0 and t >= 0.94 * T and (current_id > 0):
						final_dist = 0
			else:
				final_dist = 0
			heading = next_id[current_id][final_dist]
			dist_left = edge[current_id][heading] - 1
			command[t] = heading + 1
	for i in range(T):
		print(command[i])
	return 0
solve()


import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl = lambda : list(map(int, input().split()))
inm = lambda : map(int, input().split())
DBG = True and False
PROBL = 1
MAXVISIT = 400

def ddprint(x):
	if DBG:
		print(x)

def trigger():
	return len(pendreq) > 0

def nxtnode():
	global lastnd, workreq, nxtndary
	tgt = workreq[0] if len(workreq) > 0 else 1
	return nxtndary[lastnd][tgt]

def atdepot():
	return lastnd == 1 and distfromlast == 0

def stay():
	print(-1)
	sys.stdout.flush()

def readput():
	n = inn()
	for i in range(n):
		inn()

def readverd():
	v = input().strip()
	if v != 'OK':
		exit()
	readput()

def move():
	global distfromlast, lastnd, workreq
	nxtnd = nxtnode()
	print(nxtnd)
	sys.stdout.flush()
	distfromlast += 1
	if distfromlast == dist[lastnd][nxtnd]:
		distfromlast = 0
		if len(workreq) > 0 and nxtnd == workreq[0]:
			del workreq[0]
		lastnd = nxtnd

def setwork():
	global pendreq, workreq
	oldest = pendreq[0][1]
	pendset = set([x[1] for x in pendreq])
	sortq = []
	for i in [0, 1]:
		q = []
		base = 1 if i == 1 else oldest
		for x in pendset:
			q.append((dist[base][x], x))
		q.sort(reverse=True)
		sortq.append(q)
	vislist = []
	while len(vislist) < MAXVISIT and (len(sortq[0]) > 0 or len(sortq[1]) > 0):
		for j in [0, 1]:
			if len(sortq[j]) == 0:
				continue
			(d, x) = sortq[j].pop()
			if x in vislist or x in workreq:
				continue
			vislist.append(x)
	prev = 1
	while len(vislist) > 0:
		mn = 9999
		for (i, x) in enumerate(vislist):
			d = dist[prev][x]
			if d < mn:
				mn = d
				mni = i
		mnx = vislist[mni]
		workreq.append(mnx)
		del vislist[mni]
		prev = mnx
	pendreq = [x for x in pendreq if x[1] not in workreq]
ddprint('start')
prob = PROBL
(V, E) = inm()
es = [[] for i in range(V + 1)]
dist = [[9999] * (V + 1) for i in range(V + 1)]
for i in range(V + 1):
	dist[i][i] = 0
for i in range(E):
	(a, b, c) = inm()
	es[a].append((b, c))
	es[b].append((a, c))
	dist[a][b] = dist[b][a] = c
if DBG:
	for (i, z) in enumerate(es):
		print(str(i) + ' ' + str(z))
for k in range(1, V + 1):
	for i in range(1, V + 1):
		for j in range(1, V + 1):
			dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
ddprint('WS done')
nxtndary = [[0] * (V + 1) for i in range(V + 1)]
for i in range(1, V + 1):
	for j in range(1, V + 1):
		if j == i:
			continue
		found = False
		for z in es[i]:
			k = z[0]
			if dist[i][j] == z[1] + dist[k][j]:
				nxtndary[i][j] = k
				found = True
				break
		if not found:
			print('nxtndary ERR')
			exit()
if prob == 2:
	F = inl()
tt = inn()
pendreq = []
workreq = []
lastnd = 1
distfromlast = 0
for t in range(tt):
	if DBG and t > 3400:
		exit()
	n = inn()
	if n == 1:
		(new_id, dst) = inm()
		pendreq.append((new_id, dst))
	if prob == 2:
		readput()
	if atdepot():
		if trigger():
			setwork()
			if len(workreq) > 0:
				move()
			else:
				stay()
		else:
			stay()
	else:
		move()
	if prob == 2:
		readverd()


(V, E) = map(int, input().split())
dis = [[10 ** 10 for _ in range(V)] for _ in range(V)]
for i in range(E):
	(u, v, d) = map(int, input().split())
	dis[u - 1][v - 1] = d
	dis[v - 1][u - 1] = d

def warshall_floyd(d):
	for k in range(V):
		for i in range(V):
			for j in range(v):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
dis = warshall_floyd(dis)
t = int(input())
bag = []
for i in range(t):
	N_new = int(input())
	p = []
	for j in range(N_new):
		(id, dst) = map(int, input().split())
		p.append([id, dst])
	bag.append(p)
now = 1
for i in range(t):
	print(-1)


(V, E) = map(int, input().split())
es = [[] for i in range(V)]
for i in range(E):
	(a, b, c) = map(int, input().split())
	(a, b) = (a - 1, b - 1)
	es[a].append((b, c))
	es[b].append((a, c))
T = int(input())
for i in range(T):
	Nnew = int(input())
	for j in range(Nnew):
		(new_id, dst) = map(int, input().split())
for i in range(T):
	print(-1)


import time
st_time = time.time()
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import random

def I():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
YN = ['Yes', 'No']
mo = 10 ** 9 + 7
inf = float('inf')
ts = time.time()
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
show_flg = False

def dijkstra(edge, st):
	n = len(edge)
	d = [(0 if st == i else inf, i) for i in range(n)]
	prev = [0] * n
	q = [i for i in d]
	heapify(q)
	while q:
		(dist, cur) = heappop(q)
		for (dst, dist) in edge[cur]:
			alt = d[cur][0] + dist
			if alt < d[dst][0]:
				d[dst] = (alt, dst)
				prev[dst] = cur
				heappush(q, (alt, dst))
	dist = [i for (i, j) in d]
	return (dist, prev)
(V, E) = MI()
g = [[] for _ in range(V + 1)]
for i in range(E):
	(u, v, d) = MI()
	g[u].append((v, d))
	g[v].append((u, d))
mins = [[] for _ in range(V + 1)]
prevs = [[] for _ in range(V + 1)]
for i in range(1, V + 1):
	(min_dist, prev) = dijkstra(g, i)
	mins[i] = min_dist
	prevs[i] = prev
T = I()
order = [0] * T
accor = [0] * T
order_time = []
for i in range(T):
	n = I()
	accor[i] = accor[i - 1]
	if n > 0:
		(oid, v) = MI()
		order[i] = v
		accor[i] += 1
order_at_shop = []
item_at_car = [[] for _ in range(V + 1)]
num_item_at_car = 0

def ship():
	global num_item_at_car
	while order_at_shop:
		(v, t) = order_at_shop.pop()
		item_at_car[v].append(t)
		num_item_at_car += 1

def deliver(v, deliver_t):
	global num_item_at_car
	d_p = 0
	while item_at_car[v]:
		or_t = item_at_car[v].pop()
		num_item_at_car -= 1
		d_p += T ** 2 - (deliver_t - or_t) ** 2
	return d_p

def stat_init():
	global order_at_shop
	global item_at_car
	global num_item_at_car
	order_at_shop = []
	item_at_car = [[] for _ in range(V + 1)]
	num_item_at_car = 0

def rand_move(s, c):
	stat_init()
	move = []
	state = 0
	reached = False
	cur = 1
	point = 0
	delta = int(T * math.exp(-c / 50))
	minT = max(0, s - delta)
	maxT = min(int(0.95 * T), s + delta)
	st = random.randint(minT, maxT)
	show('---------------', st)
	for t in range(T):
		v = order[t]
		if v != 0:
			order_at_shop.append((v, t))
		if t < st:
			move.append(-1)
			ship()
		elif state == 0:
			r = len(g[cur])
			(dest, dist) = g[cur][random.randint(0, r - 1)]
			state = 1
			move.append(dest)
			dist -= 1
			if dist == 0:
				state = 0
				cur = dest
				if dest == 1:
					ship()
				else:
					point += deliver(dest, t)
		else:
			move.append(dest)
			dist -= 1
			if dist == 0:
				state = 0
				cur = dest
	return (point, st, move)

def best_deliver(cur, now):
	global order_at_shop
	global item_at_car
	global num_item_at_car
	effc = 0
	deliver_point = 1
	for dest in range(2, V + 1):
		if dest == cur:
			continue
		d = mins[cur][dest]
		rt = now + d
		alt = 0
		for j in item_at_car[dest]:
			alt += T ** 2 - (rt - j) ** 2
		if alt / d > effc:
			effc = alt / d
			deliver_point = dest
	db = mins[cur][1]
	nx_item_at_car = [[] for i in range(1 + V)]
	for (order_v, t) in order_at_shop:
		nx_item_at_car[order_v].append(t)
	for i in range(2, 1 + V):
		for t in item_at_car[i]:
			nx_item_at_car[i].append(t)
	for t in range(min(T - 1, now + 1), min(now + db + 1, T)):
		v = order[t]
		if v != 0:
			nx_item_at_car[v].append(t)
	for dest in range(2, V + 1):
		if dest == cur:
			continue
		dg = mins[1][dest]
		rt = now + dg + db
		alt = 0
		for j in nx_item_at_car[dest]:
			alt += T ** 2 - (rt - j) ** 2
		if alt / d > effc:
			effc = alt / d
			deliver_point = 1
		root = []
		p = deliver_point
		while p != cur:
			prev_p = prevs[cur][p]
			root.append((p, mins[p][prev_p]))
			p = prev_p
	return (deliver_point, root)

def greed_move():
	stat_init()
	move = []
	state = 0
	reached = False
	final_dest = 1
	dest = 1
	cur = 1
	point = 0
	for t in range(T):
		v = order[t]
		if v != 0:
			order_at_shop.append((v, t))
		if cur == 1 and state == 0:
			ship()
		if num_item_at_car == 0 and cur == 1 and (state == 0):
			move.append(-1)
			ship()
		else:
			if state == 0:
				if dest == 1:
					ship()
				else:
					point += deliver(dest, t)
				if cur == final_dest:
					(final_dest, root) = best_deliver(cur, t)
					if root:
						(dest, dist) = root.pop()
					else:
						move.append(-1)
						continue
					if dest == cur:
						dest = final_dest
				else:
					(dest, dist) = root.pop()
					if dest == cur:
						dest = final_dest
				state = 1
			else:
				0
			move.append(dest)
			dist -= 1
			show('moving to', dest)
			if dist == 0:
				state = 0
				cur = dest
	return (point, move)
mode = 'rand'
mode = 'greed'
if mode == 'rand':
	time_limit = 29.5
	time_limit = 0.07
	now = time.time()
	p = -1
	s = T // 2
	c = 1
	while True:
		c += 1
		now = time.time()
		if now - st_time > time_limit:
			break
		(cur_p, cur_st, cur_move) = rand_move(s, c)
		if cur_p > p or p == -1:
			p = cur_p
			s = cur_st
			move = cur_move
elif mode == 'greed':
	(point, move) = greed_move()
if len(move) < T:
	move += [-1] * (T - len(move))
for i in move:
	print(i)

def interactive():
	for i in range(T):
		Nnew = int(input())
		for j in range(Nnew):
			(new_id, dst) = map(int, input().split())
		Nput = int(input())
		for j in range(Nput):
			put_id = int(input())
		print(move[i])
		sys.stdout.flush()
		vardict = input()
		if vardict == 'NG':
			sys.exit()
		Nachive = int(input())
		for j in range(Nachive):
			achive_id = int(input())
	return


def empty(t_max):
	return [-1] * t_max

def main():
	(nv, ne) = map(int, input().split())
	graph_dict = dict()
	for i in range(nv):
		graph_dict[i + 1] = dict()
	for _ in range(ne):
		(u, v, d) = map(int, input().split())
		graph_dict[u][v] = d
		graph_dict[v][u] = d
	t_max = int(input())
	order_list = [[] for _ in range(t_max)]
	for t in range(t_max):
		n_new = int(input())
		for _ in range(n_new):
			(new_id, dst) = map(int, input().split())
			order_list[t].append([new_id, dst])
	res = empty(t_max)
	for r in res:
		print(r)
main()


import collections
import sys
STAY = -1
BASE_POS = 0

class Order:

	def __init__(self, order_id, ordered_time, destination):
		self.order_id = order_id
		self.ordered_time = ordered_time
		self.destination = destination

	def __str__(self):
		return 'Order' + str((self.order_id, self.ordered_time, self.destination))

class Graph:

	def __init__(self, n_vertices, n_edges):
		self.n_vertices = n_vertices
		self.n_edges = n_edges
		self.adjacency_list = [[] for i in range(n_vertices)]
		self.distances = [[float('inf')] * n_vertices for _ in range(n_vertices)]
		self.transits = [[j for j in range(n_vertices)] for i in range(n_vertices)]

	def add_edge(self, u, v, d):
		self.adjacency_list[u].append((v, d))
		self.adjacency_list[v].append((u, d))
		self.distances[u][v] = d
		self.distances[v][u] = d
		self.transits[u][v] = v
		self.transits[v][u] = u

	def floyd_warshall(self):
		for i in range(self.n_vertices):
			self.distances[i][i] = 0
			self.transits[i][i] = i
		for k in range(self.n_vertices):
			for i in range(self.n_vertices):
				for j in range(self.n_vertices):
					if self.distances[i][j] > self.distances[i][k] + self.distances[k][j]:
						self.distances[i][j] = self.distances[i][k] + self.distances[k][j]
						self.transits[i][j] = self.transits[i][k]

def get_orders(ordered_time):
	n_new_order = int(input())
	orders = []
	for _ in range(n_new_order):
		(order_id, destination) = map(int, input().split())
		orders.append(Order(order_id, ordered_time, destination - 1))
	return orders

def get_input():
	(n_vertices, n_edges) = map(int, input().split())
	graph = Graph(n_vertices, n_edges)
	for _ in range(n_edges):
		(u, v, d) = map(int, input().split())
		graph.add_edge(u - 1, v - 1, d)
	graph.floyd_warshall()
	time_max = int(input())
	orders = []
	for time_index in range(time_max):
		new_orders = get_orders(time_index)
		for order in new_orders:
			orders.append(order)
	return (graph, time_max, orders)

def solve(graph, time_max, orders):
	car_on_vertex = True
	car_pos = BASE_POS
	next_pickup = 0
	commands = [-1] * time_max
	cargo = []
	t = 0
	while t < time_max:
		if car_on_vertex and car_pos == BASE_POS:
			while next_pickup < len(orders) and orders[next_pickup].ordered_time <= t:
				cargo.append(orders[next_pickup])
				next_pickup += 1
		if cargo:
			cargo.sort(key=lambda x: (t - x.ordered_time + graph.distances[car_pos][x.destination]) ** 2)
			print(','.join([str(c) for c in cargo]), file=sys.stderr)
			dist = cargo[0].destination
			if time_max <= t + graph.distances[car_pos][dist]:
				cargo = cargo[1:]
				continue
			transit_point = graph.transits[car_pos][dist]
			need_time_for_move = graph.distances[car_pos][transit_point]
			for i in range(need_time_for_move):
				commands[t + i] = transit_point
			t += need_time_for_move
			car_pos = transit_point
			cargo = cargo[1:]
			continue
		elif car_on_vertex:
			if car_pos == BASE_POS:
				commands[t] = STAY
			else:
				transit_point = graph.transits[car_pos][BASE_POS]
				need_time_for_move = graph.distances[car_pos][transit_point]
				if time_max <= t + need_time_for_move:
					t = time_max
					break
				for i in range(need_time_for_move):
					commands[t + i] = transit_point
				t += need_time_for_move
				car_pos = transit_point
				continue
		else:
			pass
		commands[t] = STAY
		t += 1
	return commands

def simulate(graph, time_max, orders, commands):
	car_on_vertex = True
	car_pos = BASE_POS
	return 0

def main():
	(graph, time_max, orders) = get_input()
	commands = solve(graph, time_max, orders)
	for command in commands:
		if command == STAY:
			print(STAY)
		else:
			print(command + 1)
main()