#![allow(non_snake_case, unused)]

#[cfg(feature = "local")]
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]) };
}

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;
			}
		}
	}
	fn compute_best_path(&self, input: &Input, ps: &Vec<usize>) -> (usize, Vec<usize>) {
		profile!(compute_best_path);
		let mut score = 0;
		let mut t = self.t;
		let mut visited = vec![false; input.n];
		let mut max_score = vec![0; input.n];
		let mut prev = vec![!0; input.n];
		let mut vs = vec![];
		let mut command = vec![];
		for i in 0..ps.len() - 1 {
			vs.clear();
			let mut que = BinaryHeap::new();
			let len = input.dij[ps[i + 1]].dist[ps[i]];
			que.push((len, ps[i]));
			while let Some((d, u)) = que.pop() {
				vs.push(u);
				let t2 = t + (len - d) as usize;
				if !visited[u] && t2 <= input.T {
					for &s in &self.orders[u] {
						let w = t2 - s;
						max_score[u] += self.T * self.T - w * w;
					}
				}
				if u == 0 {
					max_score[u] += 1000 * self.T * self.T;
				}
				for &(v, l) in &self.g[u] {
					if input.dij[ps[i + 1]].dist[u] == input.dij[ps[i + 1]].dist[v] + l {
						if prev[v] == !0 {
							que.push((input.dij[ps[i + 1]].dist[v], v));
							max_score[v] = max_score[u];
							prev[v] = u;
						} else {
							let tmp = max_score[u];
							if max_score[v].setmax(tmp) {
								prev[v] = u;
							}
						}
					}
				}
			}
			let mut u = ps[i + 1];
			let mut us = vec![u];
			while u != ps[i] {
				u = prev[u];
				us.push(u);
			}
			us.reverse();
			for &v in &vs {
				max_score[v] = 0;
				prev[v] = !0;
			}
			vs.clear();
			for i in 0..us.len() - 1 {
				let (u, v) = (us[i], us[i + 1]);
				let d = input.dij[u].dist[v] as usize;
				for _ in 0..d {
					command.push(v);
				}
				t += d;
				if !visited[v] && t <= input.T {
					for &s in &self.orders[v] {
						let w = t - s;
						score += self.T * self.T - w * w;
					}
				}
				visited[v] = true;
			}
		}
		(score, command)
	}
}

#[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;
	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;
			}
		}
		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> {
	profile!(tsp);
	let until = until.min(TIME_LIMIT);
	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 (mut min, mut min_ps) = (cost, ps.clone());
	let mut rep = 0;
	while rep == 0 || get_time() < until {
		loop {
			rep += 1;
			let mut ok = false;
			// 2-opt
			for i in 1..n {
				for j in i+1..n {
					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();
		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;
		}
	}
	eprintln!("rep: {}", rep);
	min_ps.into_iter().map(|i| qs[i]).collect()
}

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

fn compute_paths(input: &Input, k: usize) -> Vec<Vec<usize>> {
	profile!(compute_paths);
	let mut div: Vec<_> = (0..k-1).map(|i| input.n * (i + 1) / k).collect();
	let mut g = mat![1 << 29; input.n; input.n];
	for i in 0..input.n {
		for j in 0..input.n {
			g[i][j] = input.dij[i].dist[j];
		}
	}
	let mut rng = XorShift::new(47894);
	let mut ps = greedy(input);
	let mut cost = compute_cost_with_div(&g, &ps, &div);
	eprintln!("init: {:?}", cost);
	let (mut min, mut min_ps) = (cost, ps.clone());
	let mut rep = 0;
	let until = get_time() + 5.0;
	while rep == 0 || get_time() < until {
		loop {
			rep += 1;
			let mut ok = false;
			// 2-opt
			for i in 1..input.n {
				for j in i+1..input.n {
					if j - i < input.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]];
						let orig_div = cost.0 - cost.1;
						let mut new_div = 0;
						for &p in &div {
							let p1 = if i <= p - 1 && p - 1 <= j {
								i + (j - p + 1)
							} else {
								p - 1
							};
							let p2 = if i <= p && p <= j {
								i + (j - p)
							} else {
								p
							};
							new_div += g[0][ps[p1]] + g[0][ps[p2]] - g[ps[p1]][ps[p2]];
						}
						if diff + new_div - orig_div < 0 {
							cost.0 += diff + new_div - orig_div;
							cost.1 += 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;
			}
		}
		assert_eq!(cost, compute_cost_with_div(&g, &ps, &div));
		if min.setmin(cost) {
			eprintln!("{:.3}: {:?}", get_time(), cost);
			min_ps = ps;
		}
		ps = min_ps.clone();
		if input.n < 4 {
			break;
		}
		loop {
			if rng.next(2) == 0 {
				// double bridge
				let mut is: Vec<_> = (0..4).map(|_| rng.next(input.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_with_div(&g, &ps, &div);
			} else {
				for _ in 0..6 {
					loop {
						let i = 1 + rng.next(input.n - 1) as usize;
						let j = 1 + rng.next(input.n - 1) as usize;
						if i < j && j - i < input.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_with_div(&g, &ps, &div);
			}
			break;
		}
	}
	eprintln!("rep: {}", rep);
	ps = min_ps;
	div.insert(0, 0);
	div.push(input.n + 1);
	let mut paths = vec![];
	for i in 0..div.len()-1 {
		let mut qs: Vec<_> = ps[div[i]..div[i + 1]].iter().cloned().collect();
		if i != 0 {
			qs.insert(0, 0);
		}
		if i + 1 != div.len() {
			qs.push(0);
		}
		paths.push(tsp(input, &qs, get_time() + 2.0));
	}
	paths
}

fn run() {
	let input = read_input();
	eprintln!("Problem = {}", input.problem);
	eprintln!("n = {}", input.n);
	#[cfg(feature = "local")]
	let vis = if let Some(p) = std::env::args().nth(1) {
		Some(Vis::new(&input.g, &p))
	} else {
		None
	};
	let paths = compute_paths(&input, 4);
	#[cfg(feature = "local")]
	{
		if let Some(ref vis) = vis {
			for i in 0..paths.len() {
				vis.vis(&format!("path{}.svg", i + 1), &paths[i]);
			}
		}
	}
	let mut length = 0;
	for path in &paths {
		for i in 0..path.len() - 1 {
			length += input.dij[path[i]].dist[path[i + 1]];
		}
	}
	eprintln!("length = {}", length);
	let mut i = 0;
	let mut commands = vec![];
	let mut state = State::new(&input);
	let mut tmp = 0;
	for t in 0..input.T {
		state.add_order(read_new_order());
		if input.problem == 'b' {
			let k = read!(usize);
			read!(usize; k);
		}
		if commands.len() == 0 {
			assert!(state.u == state.v);
			for _ in 0..paths.len() {
				i = (i + 1) % paths.len();
				if paths[i].iter().any(|&u| state.orders[u].len() > 0) {
					let qs: Vec<_> = paths[i].iter().filter(|&&u| u == 0 || state.orders[u].len() > 0).cloned().collect();
					let qs = tsp(&input, &qs, get_time() + 0.2);
					let p1 = state.compute_best_path(&input, &qs);
					let p2 = state.compute_best_path(&input, &qs.iter().cloned().rev().collect());
					if p1.0 > p2.0 {
						commands = p1.1;
						tmp += p1.0;
					} else {
						commands = p2.1;
						tmp += p2.0;
					}
					commands = commands.into_iter().rev().collect();
					eprintln!("targets: {}", qs.len() - 2);
					break;
				}
			}
		}
		if let Some(c) = commands.pop() {
			state.command(c);
			println!("{}", c + 1);
		} else {
			state.command(!0);
			println!("-1");
		}
		std::io::stdout().flush().unwrap();
		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