import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn = "in.txt") { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
long lcm(long x, long y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998244353;
//long mod = 1_000_003;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto N = RD;
	auto M = RD;
	auto edges = new long[2][][](N);
	foreach (i; 0..M)
	{
		auto u = RD-1;
		auto v = RD-1;
		auto d = RD;
		edges[u] ~= [v, d];
		edges[v] ~= [u, d];
	}
	auto f = RDA;
	auto T = RD;
	auto LOTime = cast(long)(T * 0.95);

	auto dist = new long[][](N);
	foreach (i; 0..N)
	{
		auto dist_ = new long[](N);
		dist_[] = long.max;
		dist_[i] = 0;
		auto open = heapify!((long a, long b) => dist_[a] > dist_[b])(new long[](N), 0);
		open.insert(i);
		while (!open.empty)
		{
			auto u = open.front; open.removeFront;
			foreach (e; edges[u])
			{
				auto v = e[0];
				auto d = e[1];
				if (dist_[u]+d < dist_[v])
				{
					dist_[v] = dist_[u] + d;
					open.insert(v);
				}
			}
		}
		dist[i] = dist_;
	}
	//debug writeln("dist done");

	long[3] pos;
	long[][long] newStack, putStack;
	long newCnt, putCnt;
	bool isFile;
	debug isFile = true;

	long computeDist(long dst)
	{
		long d;
		if (pos[2] == 0)
			d = dist[pos[0]][dst];
		else
		{
			auto d1 = dist[pos[0]][dst] + pos[2];
			auto d2 = dist[pos[1]][dst] + dist[pos[0]][pos[1]] - pos[2];
			d       = min(d1, d2);
		}
		return d;
	}
	long computeExp(long d, long elapsed)
	{
		long wait = elapsed + d;
		return (T^^2) - (wait^^2);
	}
	long[] computeBestDst(long time)
	{
		long score, dst;
		foreach (key; putStack.keys)
		{
			long s;
			foreach (e; putStack[key])
				s += computeExp(computeDist(key), time-e);
			if (s > score)
			{
				score = s;
				dst   = key;
			}
		}
		return [score, dst];
	}
	
	long lastDst;
	foreach (i; 0..T)
	{
		bool isLastMode()
		{
			return i >= LOTime && newCnt <= 8;
		}

		auto N1 = RD;
		foreach (_; 0..N1)
		{
			auto id = RD;
			auto dst = RD-1;
			newStack[dst] ~= i;
		}
		newCnt += N1;
		auto N2 = RD;
		foreach (_; 0..N2) auto id = RD;

		long dst;
		if (isLastMode())
		{
			dst = lastDst;
		}
		if (pos[2] == 0)
		{
			if (pos[0] == 0)
			{
				foreach (key; newStack.keys)
					putStack[key] ~= newStack[key];
				long[][long] dummy;
				newStack = dummy;
				putCnt += newCnt;
				newCnt = 0;
			}

			auto putKeys = putStack.get(pos[0], []);
			if (!putKeys.empty || pos[0] == 0)
			{
				putCnt -= putKeys.length;
				putStack.remove(pos[0]);
				if (isLastMode())
				{
					auto psKeys = putStack.keys;
					auto len = psKeys.length;
					auto expList = new long[](len);
					foreach (j; 0..len)
					{
						auto keys = psKeys.dup; swap(keys[0], keys[j]);
						auto u = keys[0];
						long time = i;
						auto d = computeDist(u);
						if (time+d > T+1) continue;
						foreach (e; putStack[u])
						{
							auto exp = computeExp(d, time-e);
							//foreach (k; 0..len)
								expList[j] += exp;
						}
						time += d;
						//foreach (l; 1..len)
						{
							/*auto time2 = time;
							auto keys2 = keys.dup; swap(keys2[1], keys2[l]);
							auto u2 = keys2[1];
							if (time2+dist[u][u2] > T) continue;
							foreach (e; putStack[u2])
								expList[j*len+l] += computeExp(dist[u][u2], time2-e);
							time2 += dist[u][u2];*/

							foreach (k; 1..len)
							{
								long p;
								double best = 0.0;
								foreach (ki; k..len)
								{
									double exp = 0.0;
									foreach (e; putStack[keys[ki]])
										exp += cast(double)computeExp(dist[u][keys[ki]], time-e);
									exp /= dist[u][keys[ki]];
									if (exp > best)
									{
										best = exp;
										p = ki;
									}
								}
								swap(keys[k], keys[p]);
								auto v = keys[k];
								if (time+dist[u][v] > T+1) break;
								foreach (e; putStack[v])
									expList[j] += computeExp(dist[u][v], time-e);
								time += dist[u][v];
								u = v;
							}
						}
					}
					auto p = expList.MIN_POS!"a > b";
					if (!psKeys.empty)
						dst = psKeys[p];
				}
			}
		}

		if (!isLastMode())
		{
			double stackRatio = 10000.0;
			double LORatio = 1.0 + 0.03 * max(1000 - (LOTime - i), 0);
			//double LORatio = 1.1 + 10.0 * max(i - LOTime, 0);
			if (putCnt != 0)
				stackRatio = cast(double)newCnt / putCnt * max(1.0, newCnt / 11.0) * LORatio;
				//stackRatio = cast(double)newCnt / putCnt * LORatio;
			auto recallExp = 0.0;
			auto recallD   = computeDist(0);
			if (recallD != 0)
				recallExp = (1.0 / recallD) * stackRatio + (1.0 / recallD) * stackRatio * 0.066;

			auto keys = putStack.keys;
			auto expList = new double[](keys.length);
			foreach (j; 0..keys.length)
			{
				auto v = keys[j];
				expList[j]  = 1.0 / (cast(double)computeDist(v) / putStack[v].length);
				expList[j] += (1.0 / dist[v][0]) * stackRatio * 0.066;
				/*double second = 0.0;
				foreach (key; putStack.keys)
				{
					if (key == v) continue;
					second = max(second, 1.0 / (cast(double)dist[v][key] / putStack[key].length));
				}
				expList[j] += second * 1.0;*/

				double w = 0.0;
				foreach (e; putStack[v])
					w = (i - e)^^2;
				auto waitingExp = 1.0 / (1.0 + exp(-w));
				if (i >= 8000)
					waitingExp = 1.5 - waitingExp;
				expList[j] += waitingExp * 0.1;
			}
			auto p = expList.MIN_POS!"a > b";
			if (!keys.empty)
				if (expList[p] > recallExp)
					dst = keys[p];
		}

		long w;
		if (pos[0] == dst && pos[2] == 0)
			w = -1;
		else if (pos[2] != 0)
		{
			auto d1 = dist[pos[0]][dst] + pos[2];
			auto d2 = dist[pos[1]][dst] + dist[pos[0]][pos[1]] - pos[2];
			if (d1 < d2)
				w = pos[0];
			else
				w = pos[1];
		}
		else
		{
			long best = long.max;
			foreach (e; edges[pos[0]])
			{
				auto d = e[1] + dist[e[0]][dst];
				if (d < best)
				{
					best = d;
					w = e[0];
				}
			}
			pos[1] = w;
		}
		if (w != -1)
		{
			if (w == pos[1])
				++pos[2];
			else
				--pos[2];
			if (pos[2] == dist[pos[0]][pos[1]])
			{
				pos[0] = pos[1];
				pos[2] = 0;
			}
		}

		lastDst = dst;
		//stderr.writeln("i:", i, " ", pos);
		writeln(w == -1 ? w : w+1);
		stdout.flush();
		auto verdict = RD!string;
		if (verdict == "NG")
		{
			//stderr.writeln(edges[pos[0]]);
			break;
		}
		auto N3 = RD;
		foreach (_; 0..N3) auto id = RD;
	}

	stdout.flush();
	//debug readln();
}

Measured memory_bytes: 9676