#![allow(non_snake_case, unused)]

#[cfg(feature = "local")]
#[macro_use]
extern crate hokudai19;

#[cfg(feature = "local")]
use hokudai19::*;

#[cfg(not(feature = "local"))]
macro_rules! profile {
	($id:ident) => {
	};
}

use std::collections::*;
use std::io::prelude::*;

////////// missing functions in 1.15.1 //////////
macro_rules! eprint {
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = write!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! eprintln {
	() => { eprintln!(""); };
	($($t:tt)*) => {{
		use ::std::io::Write;
		let _ = writeln!(::std::io::stderr(), $($t)*);
	}};
}
macro_rules! dbg {
	($v:expr) => {{
		let val = $v;
		eprintln!("[{}:{}] {} = {:?}", file!(), line!(), stringify!($v), val);
		val
	}}
}
/////////////////////////////////////////////////
pub trait SetMinMax {
	fn setmin(&mut self, v: Self) -> bool;
	fn setmax(&mut self, v: Self) -> bool;
}
impl<T> SetMinMax for T where T: PartialOrd {
	fn setmin(&mut self, v: T) -> bool {
		*self > v && { *self = v; true }
	}
	fn setmax(&mut self, v: T) -> bool {
		*self < v && { *self = v; true }
	}
}

macro_rules! mat {
	($($e:expr),*) => { Vec::from(vec![$($e),*]) };
	($($e:expr,)*) => { Vec::from(vec![$($e),*]) };
	($e:expr; $d:expr) => { Vec::from(vec![$e; $d]) };
	($e:expr; $d:expr $(; $ds:expr)+) => { Vec::from(vec![mat![$e $(; $ds)*]; $d]) };
}

macro_rules! ok {
	($a:ident$([$i:expr])*.$f:ident()$(@$t:ident)*) => {
		$a$([$i])*.$f($($t),*)
	};
	($a:ident$([$i:expr])*.$f:ident($e:expr$(,$es:expr)*)$(@$t:ident)*) => { {
		let t = $e;
		ok!($a$([$i])*.$f($($es),*)$(@$t)*@t)
	} };
}

pub fn readln() -> String {
	let mut line = String::new();
	::std::io::stdin().read_line(&mut line).unwrap_or_else(|e| panic!("{}", e));
	line
}

macro_rules! read {
	($($t:tt),*; $n:expr) => {{
		let stdin = ::std::io::stdin();
		let ret = ::std::io::BufRead::lines(stdin.lock()).take($n).map(|line| {
			let line = line.unwrap();
			let mut it = line.split_whitespace();
			_read!(it; $($t),*)
		}).collect::<Vec<_>>();
		ret
	}};
	($($t:tt),*) => {{
		let line = readln();
		let mut it = line.split_whitespace();
		_read!(it; $($t),*)
	}};
}

macro_rules! _read {
	($it:ident; [char]) => {
		_read!($it; String).chars().collect::<Vec<_>>()
	};
	($it:ident; [u8]) => {
		Vec::from(_read!($it; String).into_bytes())
	};
	($it:ident; usize1) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1
	};
	($it:ident; [usize1]) => {
		$it.map(|s| s.parse::<usize>().unwrap_or_else(|e| panic!("{}", e)) - 1).collect::<Vec<_>>()
	};
	($it:ident; [$t:ty]) => {
		$it.map(|s| s.parse::<$t>().unwrap_or_else(|e| panic!("{}", e))).collect::<Vec<_>>()
	};
	($it:ident; $t:ty) => {
		$it.next().unwrap_or_else(|| panic!("input mismatch")).parse::<$t>().unwrap_or_else(|e| panic!("{}", e))
	};
	($it:ident; $($t:tt),+) => {
		($(_read!($it; $t)),*)
	};
}

pub fn main() {
	let _ = ::std::thread::Builder::new().name("run".to_string()).stack_size(32 * 1024 * 1024).spawn(run).unwrap().join();
}

////////// for marathon competitions //////////

pub struct XorShift {
	pub x: [u32; 4]
}

impl XorShift {
	pub fn new(mut seed: u32) -> XorShift {
		let mut x = [0; 4];
		for i in 0..4 {
			seed = 1812433253u32.wrapping_mul(seed ^ (seed >> 30)).wrapping_add(i as u32);
			x[i] = seed;
		}
		XorShift { x: x }
	}
	pub fn next32(&mut self) -> usize {
		let t = self.x[0] ^ (self.x[0] << 11);
		for i in 0..3 { self.x[i] = self.x[i + 1] }
		self.x[3] = self.x[3] ^ (self.x[3] >> 19) ^ t ^ (t >> 8);
		self.x[3] as usize
	}
	/// [0, n)
	pub fn next(&mut self, n: usize) -> usize {
		loop {
			let t = self.next32();
			let r = t % n;
			if (t - r).checked_add(n).is_some() {
				return r;
			}
		}
	}
}

fn get_time() -> f64 {
	static mut STIME: f64 = -1.0;
	let t = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
	let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
	unsafe {
		if STIME < 0.0 {
			STIME = ms;
		}
		ms - STIME
	}
}

/////////////////////////////////////////////////

const TIME_LIMIT: f64 = 29.0;

type Graph = Vec<Vec<(usize, i32)>>;

#[derive(Clone, Debug)]
struct Input {
	n: usize,
	g: Graph,
	f: Vec<i32>,
	T: usize,
	problem: char,
	dij: Vec<Dijkstra>
}

fn read_input() -> Input {
	let (n, m) = read!(usize, usize);
	get_time();
	let mut g = vec![vec![]; n];
	for (u, v, d) in read!(usize1, usize1, i32; m) {
		g[u].push((v, d));
		g[v].push((u, d));
	}
	let (f, T, problem) = {
		let f = read!([i32]);
		if f[0] > 2 {
			(vec![], f[0] as usize, 'a')
		} else {
			(f, read!(usize), 'b')
		}
	};
	let mut dij = vec![];
	for i in 0..n {
		dij.push(Dijkstra::compute(&g, i));
	}
	Input { n: n, g: g, f: f, T: T, problem: problem, dij: dij }
}

fn read_new_order() -> usize {
	let n = read!(usize);
	if n == 0 {
		!0
	} else {
		let (_, id) = read!(usize1, usize1);
		id
	}
}

struct State {
	g: Graph,
	T: usize,
	orders: Vec<Vec<usize>>,
	score: usize,
	t: usize,
	received: usize,
	u: usize,
	v: usize,
	dist_u: i32,
	dist_v: i32,
}

impl State {
	fn new(input: &Input) -> Self {
		State { g: input.g.clone(), T: input.T, orders: vec![vec![]; input.n], score: 0, t: 0, received: 0, u: 0, v: 0, dist_u: 0, dist_v: 0 }
	}
	fn add_order(&mut self, v: usize) {
		if v != !0 {
			self.orders[v].push(self.t);
		}
	}
	fn command(&mut self, v: usize) {
		if v != !0 {
			if self.u == self.v {
				for &(w, l) in &self.g[self.u] {
					if w == v {
						self.v = w;
						self.dist_u = 0;
						self.dist_v = l;
					}
				}
				assert!(self.u != self.v);
			}
			if self.u == v {
				std::mem::swap(&mut self.u, &mut self.v);
				std::mem::swap(&mut self.dist_u, &mut self.dist_v);
			}
			assert!(self.v == v);
			self.dist_u += 1;
			self.dist_v -= 1;
			if self.dist_v == 0 {
				self.u = self.v;
				self.dist_u = 0;
			}
		}
		self.t += 1;
		if self.u == self.v {
			if self.u == 0 {
				self.received = self.t;
				if v == 0 {
					eprintln!("home: {}", self.t);
				}
			} else {
				let mut rem = vec![];
				for &t in &self.orders[self.u] {
					if t <= self.received {
						let w = self.t - t;
						self.score += self.T * self.T - w * w;
					} else {
						rem.push(t);
					}
				}
				self.orders[self.u] = rem;
			}
		}
	}
}

#[derive(Clone, Debug)]
struct Dijkstra {
	dist: Vec<i32>,
	prev: Vec<usize>,
}

impl Dijkstra {
	fn compute(g: &Graph, s: usize) -> Self {
		profile!(dijkstra);
		let n = g.len();
		let mut dist = vec![i32::max_value(); n];
		let mut prev = vec![!0; n];
		let mut que = BinaryHeap::new();
		que.push((0, s));
		dist[s] = 0;
		while let Some((d, u)) = que.pop() {
			let d = -d;
			if dist[u] != d {
				continue;
			}
			for &(v, l) in &g[u] {
				if dist[v].setmin(d + l) {
					prev[v] = u;
					que.push((-dist[v], v));
				}
			}
		}
		Dijkstra { dist: dist, prev: prev }
	}
}

fn greedy(input: &Input) -> Vec<usize> {
	let mut ps = vec![0];
	let mut used = vec![false; input.n];
	used[0] = true;
	let mut total = 0;
	for i in 0..input.n-1 {
		let mut to = !0;
		let mut cost = i32::max_value();
		for j in 0..input.n {
			if !used[j] && cost.setmin(input.dij[ps[i]].dist[j]) {
				to = j;
			}
		}
		total += cost;
		used[to] = true;
		ps.push(to);
	}
	ps.push(0);
	ps
}

fn compute_cost(g: &Vec<Vec<i32>>, ps: &Vec<usize>) -> i32 {
	let mut tmp = 0;
	for i in 0..ps.len() - 1 {
		tmp += g[ps[i]][ps[i + 1]];
	}
	tmp
}

fn tsp(input: &Input, qs: &[usize], until: f64) -> Vec<usize> {
	let mut id = vec![!0; input.n];
	for i in 0..qs.len() - 1 {
		id[qs[i]] = i;
	}
	let n = qs.len() - 1;
	let mut g = mat![1 << 29; n; n];
	for i in 0..n {
		for j in 0..n {
			g[i][j] = input.dij[qs[i]].dist[qs[j]];
		}
	}
	let mut rng = XorShift::new(47894);
	let mut ps: Vec<_> = (0..n).chain(0..1).collect();
	let mut cost = compute_cost(&g, &ps);
	eprintln!("init: {}", cost);
	let stime = get_time();
	let (mut min, mut min_ps) = (cost, ps.clone());
	while get_time() < until {
		loop {
			let mut ok = false;
			for i in 1..n {
				for j in i+1..n {
					// 2-opt
					if j - i < n - 2 {
						let diff = g[ps[i - 1]][ps[j]] + g[ps[i]][ps[j + 1]] - g[ps[i - 1]][ps[i]] - g[ps[j]][ps[j + 1]];
						if diff < 0 {
							cost += diff;
							ps = ps[0..i].iter().chain(ps[i..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
							ok = true;
						}
					}
				}
			}
			if !ok {
				break;
			}
		}
		if min.setmin(cost) {
			eprintln!("{:.3}: {}", get_time(), cost);
			min_ps = ps;
		}
		ps = min_ps.clone();
		cost = min;
		if n < 4 {
			break;
		}
		loop {
			if rng.next(2) == 0 {
				// double bridge
				let mut is: Vec<_> = (0..4).map(|_| rng.next(n)).collect();
				is.sort();
				if is[0] == is[1] || is[1] == is[2] || is[2] == is[3] {
					continue;
				}
				ps = ps[0..is[0]+1].iter()
						.chain(ps[is[2]+1..is[3]+1].iter())
						.chain(ps[is[1]+1..is[2]+1].iter())
						.chain(ps[is[0]+1..is[1]+1].iter())
						.chain(ps[is[3]+1..].iter())
						.cloned().collect();
				cost = compute_cost(&g, &ps);
			} else {
				for _ in 0..6 {
					loop {
						let i = 1 + rng.next(n - 1) as usize;
						let j = 1 + rng.next(n - 1) as usize;
						if i < j && j - i < n - 2 {
							ps = ps[0..i].iter().chain(ps[i..j+1].iter().rev()).chain(ps[j+1..].iter()).cloned().collect();
							break;
						}
					}
				}
				cost = compute_cost(&g, &ps);
			}
			break;
		}
	}
	min_ps.into_iter().map(|i| qs[i]).collect()
}

fn run() {
	let input = read_input();
	eprintln!("Problem = {}", input.problem);
	eprintln!("n = {}", input.n);
	let path0 = tsp(&input, &greedy(&input), get_time() + 5.0);
	let mut path = vec![];
	let k = 4;
	for i in 0..k {
		let mut tmp = Vec::from(&path0[path0.len() * i / k .. path0.len() * (i + 1) / k]);
		if i != 0 {
			tmp.insert(0, 0);
		}
		if i + 1 != k {
			tmp.push(0);
		}
		path.extend(tsp(&input, &tmp, get_time() + 2.0));
		if i + 1 != k {
			path.pop();
		}
	}
	let mut length = 0;
	let p = path.len() - 1;
	for i in 0..p {
		length += input.dij[path[i]].dist[path[i + 1]];
	}
	eprintln!("length = {}", length);
	let mut i = 0;
	let mut to = 0;
	let mut state = State::new(&input);
	for t in 0..input.T {
		state.add_order(read_new_order());
		if input.problem == 'b' {
			let k = read!(usize);
			read!(usize; k);
		}
		if state.u == state.v {
			if to == path[i] {
				for _ in 0..p {
					i = (i + 1) % p;
					if state.orders[path[i]].iter().any(|&t| t <= state.received) || state.u != 0 && path[i] == 0 {
						break;
					}
				}
			}
			if path[i] != state.u {
				to = input.dij[path[i]].prev[state.u];
			}
		}
		if state.u == state.v && state.u == 0 && to == 0 {
			state.command(!0);
			println!("-1");
		} else {
			state.command(to);
			println!("{}", to + 1);
		}
		std::io::stdout().flush();
		if input.problem == 'b' {
			assert_eq!("OK", read!(String));
			let k = read!(usize);
			read!(usize; k);
		}
	}
	eprintln!("Score = {}", state.score);
	eprintln!("Time = {:.3}", get_time());
	eprintln!("fail = {}", state.orders.iter().map(|a| a.len()).sum::<usize>());
	#[cfg(feature = "local")]
	write_profile(&mut std::io::stderr());
}


Measured memory_bytes: 11344