#![allow(unused_imports)]
#![allow(non_snake_case, unused)]

use std::cmp::*;
use std::collections::*;
use std::ops::*;
use std::fmt;

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
	}}
}

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();
}

/////////////////// ここから ///////////////////////////
const TIME_LIMIT: f64 = 28.0;
const MOD: u32 = 1_000_000_007;

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
	}
}

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;
			}
		}
	}
}

// Rustのバージョン的にrotate_left()が使えない
// アップデートに期待
pub trait Rotate {
	fn rotate_left(&mut self, len: usize);
}
impl Rotate for [usize]{
	fn rotate_left(&mut self, len: usize) {
		let SL = self.len();
		let mut saved_vec = vec![0;len];
		saved_vec.copy_from_slice(&self[0..len]);
		for i in 0..SL {
			let a = i;
			let b = i+len;
			if b>SL-1 {break;}
			self[a] = self[b];
		}
		self[SL-len..SL].copy_from_slice(&saved_vec);
	}
}

struct Input {
	V: usize,
	E: usize,
	T: usize,
	edge: Vec<Vec<(usize,usize)>>,
	order: Vec<(usize,usize)>,
	closest: Vec<Vec<usize>>,
	dist: Vec<Vec<i64>>,
	prev: Vec<Vec<usize>>,
	log: Vec<f64>,
	rng: XorShift,
}

impl Input {
	fn new(V: usize, E: usize, T: usize, edge: Vec<Vec<(usize,usize)>>, order: Vec<(usize,usize)>) -> Self {
		Input {
			V: V,
			E: E,
			T: T,
			edge: edge,
			order: order,
			closest: vec![vec![1000000000;V];V],
			dist: vec![vec![]; V],
			prev: vec![vec![]; V],
			log: vec![0.0;131072],
			rng: XorShift::new(583290),
		}
	}

	fn init(&mut self){
		self.calc_closest();
		self.dij();
		self.init_log();
	}

	fn calc_closest(&mut self) {
		let mut g = vec![vec![1000000000;self.V];self.V];
		for i in 0..self.V{
			g[i][i] = 0;
		}
		for i in 0..self.V {
			for &e in &self.edge[i] {
				let s = i;
				let t = e.0;
				let d = e.1;
				g[s][t] = d;
				g[t][s] = d;
			}
		}
		for k in 0..self.V {
			for i in 0..self.V {
				for j in 0..self.V {
					g[i][j] = std::cmp::min(g[i][j], g[i][k] + g[k][j]);
				}
			}
		}
		self.closest = g;
	}

	fn dij(&mut self) {
		for i in 0..self.V{
			let (dist, prev) = dijkstra(i, &self.edge);
			self.dist[i] = dist;
			self.prev[i] = prev;
		}
	}

	fn print_closest(&self) {
		for i in 0..self.V {
			for j in 0..self.V {
				eprint!("{} ", self.closest[i][j]);
			}
			eprintln!();
		}
	}

	fn init_log(&mut self){
		for i in 0..self.log.len() {
			self.log[i] = ((i as f64 + 0.5)/self.log.len() as f64).log2();
		}
	}
}

fn dijkstra(start: usize, edge: &Vec<Vec<(usize,usize)>>) -> (Vec<i64>, Vec<usize>){
    let n = edge.len() as usize;
    let mut dist = vec![1000000000 as i64;n]; //初期値は最大距離
    dist[start] = 0;
	let mut prev = vec![n;n];
    let mut heap = BinaryHeap::new();
    heap.push((0, start));
    while let Some((pop_cost, v)) = heap.pop() {
        let cur_cost = -pop_cost;
        if dist[v] < cur_cost {continue;} //これがないと遅い
        for &(next, cost) in edge[v].iter(){
            let next_cost = cur_cost + cost as i64;
			if dist[next] > next_cost {
				dist[next] = next_cost;
				prev[next] = v;
				heap.push((-next_cost, next));
			}
        }
    }
    (dist, prev)
}

////////////////// TSP ////////////////////////////

// 適当に巡回路を見つける
fn calc_TSP(v: &HashSet<usize>, input: &Input) -> (usize, Vec<usize>) {
	let mut cur = 0;
    let mut list = vec![];
	let mut route = vec![];
	// 先頭に店を追加
	route.push(cur);
    for &i in v.iter() {
        list.push(i);
    }
    let mut dist = 0;
    for i in 0..input.V {
        if list.len()==0 {break;}
        let (idx, ret) = find_closest(cur, &list, &input);
        dist += ret;
        cur = idx;
		route.push(cur);
        let mut nlist = vec![];
        for &j in &list {
            if j==cur {continue;}
            nlist.push(j);
        }
        list = nlist;
    }
	dist += find_closest(cur, &[0], &input).1;
	route.push(0);
    // println!("{}", dist);
	(dist, route)
}

// TSPから、使ってないノードを削除する
fn clean_unused_nodes_TSP(v: &HashSet<usize>, input: &Input, route: &[usize]) -> (usize, Vec<usize>) {
	let mut nroute = vec![];
    let mut dist = 0;
	let mut cur = 0;
	// 先頭に店を追加
	nroute.push(0);
	for &i in route {
		if i==0 {continue;}
		if !v.contains(&i) {continue;}
		dist += input.closest[cur][i];
		nroute.push(i);
		cur = i;
	}
	dist += input.closest[cur][0];
	nroute.push(0);
	(dist, nroute)
}

// 2-optで巡回経路長を短くする
fn improve_TSP(route: Vec<usize>, mut input: &mut Input, target_step: usize, ordered_time_list: &Vec<Vec<usize>>) -> Vec<usize> {
	let mut nroute = route.clone();
	let mut count = 0;
	let mut swap = 0;
	let mut rem = 0.0;
	let K = 0.1;
	let start_time = get_time();
	let ROUTE_LEN = route.len();
	let LOG_LEN = input.log.len();

	let mut tl = TIME_LIMIT * min(target_step,10000) as f64 / input.T as f64 - start_time;
	if target_step <= 8000 && tl<=TIME_LIMIT/100.0 {tl=TIME_LIMIT/100.0;}
	if target_step==0 {tl=TIME_LIMIT/100.0;}
	if target_step >= 9500 && tl<=0.0 {tl=0.5;}
	// eprintln!("tl {}", tl);
	let mut t = get_time()-start_time;
	loop {
		if (count & 511) == 0 {
			t = get_time()-start_time;
			if t >= tl {break;}
			rem = (tl as f64 - t as f64) * K / tl as f64;
		}
		count += 1;

		if count%3!=0 {
			let s1_idx = input.rng.next(ROUTE_LEN-1);
			let t1_idx = input.rng.next(ROUTE_LEN-1);
			if t1_idx<=s1_idx+1 {continue;}
			
			// s1->s2...t1->t2
			let s1 = nroute[s1_idx];
			let s2 = nroute[s1_idx+1];
			let t1 = nroute[t1_idx];
			let t2 = nroute[t1_idx+1];
			if s1==0 && t2==0 {continue;} // この場合、経路が逆順になるだけなので無視
			let prev_cost = input.closest[s1][s2] + input.closest[t1][t2];
			let after_cost = input.closest[s1][t1] + input.closest[s2][t2];
			let gain = (prev_cost as f64 - after_cost as f64)/ prev_cost as f64;
			if gain < input.log[input.rng.next(LOG_LEN)] * rem {
				continue;
			}
			swap+=1;		
			// s1->s2...t1->t2
			nroute[s1_idx+1..t1_idx+1].reverse(); // s1->t1...s2->t2
		}
		else { // or-opt
			if ROUTE_LEN<=4 {continue;}
			let r1_start = input.rng.next(ROUTE_LEN-4);
			let r1_end = r1_start + input.rng.next(3) + 2;
		    let r2 = input.rng.next(ROUTE_LEN-1);
			if r2 <= r1_end {continue;}
			
			// s1          s4
			//  \         /
			//   s2->..->s3 
			//
			// t2<---------t1   
		    let s1 = nroute[r1_start];
		    let s2 = nroute[r1_start+1];
		    let s3 = nroute[r1_end-1];
		    let s4 = nroute[r1_end];
		    let t1 = nroute[r2];
			let t2 = nroute[r2+1];
			
			let mut prev_cost = 0;
			prev_cost += input.closest[s1][s2];
			prev_cost += input.closest[s3][s4];
			prev_cost += input.closest[t1][t2];
 
			let mut after_cost = 0;
			after_cost += input.closest[s1][s4];
			after_cost += input.closest[t1][s3];
			after_cost += input.closest[t2][s2];
 
		    let gain = (prev_cost as f64 - after_cost as f64)/ prev_cost as f64;
		    if gain < input.log[input.rng.next(LOG_LEN)] * rem {
		    	continue;
			}
			
			swap+=1;
			
			// if prev_cost > after_cost {eprintln!("or-opt {} {}", prev_cost, after_cost);}
			
			nroute[r1_start+1..r2+1].rotate_left(r1_end-r1_start-1); // ->s1->s4->t1->s2->s3->t2->
			nroute[r2-(r1_end-r1_start-2)..r2+1].reverse(); // ->s1->s4->t1->s3->s2->t2->
 
			// if r1_end-r1_start-1>=2 {eprintln!("or-opt: size {}", r1_end-r1_start-1);}
		    // eprintln!("prev_dist {} after_dist {}", route_dist(&nroute, &input), route_dist(&troute, &input));
		}
	}
	// 逆順にしてスコアが上がるかどうか確認する
	let mut prev_dist = target_step;
	let mut prev_score = 0;
	for i in 0..nroute.len()-1 {
		let s = nroute[i];
		let t = nroute[i+1];
		prev_dist += input.closest[s][t];
		for &j in &ordered_time_list[t] {
			prev_score += input.T.pow(2) - (prev_dist-j).pow(2);
		}
	}
	let mut after_dist = target_step;
	let mut after_score = 0;
	for i in (1..nroute.len()).rev() {
		let s = nroute[i];
		let t = nroute[i-1];
		after_dist += input.closest[s][t];
		for &j in &ordered_time_list[t] {
			after_score += input.T.pow(2) - (after_dist-j).pow(2);
		}
	}
	if after_score > prev_score {
		nroute.reverse();
		// eprintln!("improve score {}", after_score-prev_score);
	}
	nroute
}

fn find_closest(cur: usize, list: &[usize], input: &Input) -> (usize, usize){
	let mut ret = 1000000000;
	let mut idx = input.V;
	for &i in list{
		let dist = input.closest[cur][i];
		if dist < ret {
			ret = dist;
			idx = i;
		}
	}
	(idx, ret)
}

fn route_dist(route: &[usize], input: &Input) -> usize {
	let mut res = 0;
	for i in 0..route.len()-1 {
		let source = route[i];
		let target = route[i+1];
		res += input.closest[source][target];
	}
	res
}

fn calc_optimal_route_dist(set: &HashSet<usize>, mut input: &mut Input) -> (Vec<usize>, usize){
	let (mut tmp_dist, tmp_route) = calc_TSP(&set, &input);
	let mut dummy = vec![vec![0];input.V];
	let mut tmp_nroute = improve_TSP(tmp_route, &mut input, 0, &dummy);
	let dist = route_dist(&tmp_nroute, &input);
	(tmp_nroute, dist)
}

////////////////// 品物配達 ////////////////////////////

fn delever_items(route: &[usize], input: &Input, count: usize, mut ordered_time_list: &mut Vec<Vec<usize>>, 
                 mut delevered: &mut usize, mut cur_time: &mut usize, mut visited_node: &mut [bool],
				 mut score : &mut usize) {
	let mut c = count;
	for i in 0..route.len()-1 {
		let source = route[i];
		let target = route[i+1];
		print_path(source, target, &input, &mut c, &mut ordered_time_list, &mut delevered, 
		           &mut cur_time, &mut visited_node, &mut score);
	}
}

fn print_path(s: usize, t: usize, input: &Input, count: &mut usize, mut ordered_time_list: &mut Vec<Vec<usize>>,
			  mut delevered: &mut usize, mut cur_time: &mut usize, mut visited_node: &mut [bool],
			  mut score : &mut usize){
	if *count >= input.T {return;}
	let dist = input.dist[s].clone();
	let prev = input.prev[s].clone();
	let mut list = VecDeque::new();
	let mut cur = t;
	list.push_front(cur);
	loop {
		let target = prev[cur];
		list.push_front(target);
		if target==s {break;}
		cur = target;
	}
	cur = s;
	for i in 1..list.len() {
		let target = list[i];
		let dist = input.closest[cur][target];
		for j in 0..dist {
			println!("{}", target+1);
			*cur_time += 1;
			*count += 1;
			if *count >= input.T {return;}
		}
		visited_node[target] = true;
		for &j in &ordered_time_list[target] {
			*delevered += 1;
			*score += input.T.pow(2) - (*cur_time-j).pow(2);
		}
		ordered_time_list[target] = vec![];
		cur = target;
	}
}

fn print_stay() {
	println!("{}", -1);
}

fn print_route_idx(route: &[usize], idx: &[usize]) {
	for &i in idx {
		eprint!("{}: {} ", i, route[i]);
	}
	eprintln!();
}


////////////////// ノード分割 ////////////////////////////

fn split_nodes(mut input: &mut Input, group_num: usize) -> (Vec<usize>, Vec<Vec<usize>>, usize){
    let mut ret = vec![0;input.V];
	let mut diff_max = 1000000000;
	let mut diff_sum = 0;
	let mut ret_route_list = vec![vec![]; group_num];
	let mut count = 0;
	loop{
		let mut center = vec![0;group_num];
		for j in 0..group_num {
			center[j] = input.rng.next(input.V);
		}
		let mut group = vec![group_num;input.V];
		// 店を除く各頂点を、一番近い中心のグループに分類
		for i in 1..input.V {
			let mut min_dist = 1000000000;
			for j in 0..group_num {
				let dist = input.closest[i][center[j]];
				if dist<=min_dist {
					min_dist = dist;
					group[i] = j;
				}
			}
		}
		let mut item_num = vec![0;group_num];
		for i in 1..input.V {
			item_num[group[i]] += 1;
		}
		item_num.sort();
		let item_diff = item_num[group_num-1] - item_num[0];
		if item_diff>=3{continue;}

		count += 1;

		// 経路長の総和が短いグループ分けを選ぶ
		let mut dist = 0;
		let mut val_max = 0;
		let mut tmp_route_list = vec![vec![];group_num];
		for k in 0..group_num {
			let mut set = HashSet::new();
			for j in 1..input.V {
				if group[j]==k {
					set.insert(j);
				}
			}
			let (route, val) = calc_optimal_route_dist(&set, &mut input);
			tmp_route_list[k] = route;
			dist += val;
			val_max = max(val_max, val);
			eprint!("{} ", center[k]);
		}
		eprintln!("dist {}", dist);
		if dist <= diff_max {
			diff_max = dist;
			ret = group;
			ret_route_list = tmp_route_list;
			diff_sum = dist;
		}
		if (get_time()>=TIME_LIMIT / 3.0) {break;}
	}

    let mut item_num = vec![0;input.V];  
    for i in 0..input.V {
        item_num[ret[i]] += 1;
    }
    // for i in 0..group_num {
    //     eprintln!("item_num {}", item_num[i]);
    // }

    (ret, ret_route_list, diff_sum/group_num)
}

////////////////// 本体 ////////////////////////////

fn solve(mut input: &mut Input){
	let ITEM_STEP = 10;
	let mut next_time = ITEM_STEP;
	let mut wait_time = next_time;

	let mut idx = 0;
	let mut total_delevered = 0;
	let mut total_order = 0;
	let mut total_score = 0;

	let mut group_num = 3;
	let mut group_delevered = vec![];
	let (mut group, route_list, mut group_mean_dist) = split_nodes(&mut input, group_num);
	let mut ordered_time_list = vec![vec![];input.V];

	let mut center = 0;

	let mut try_delever_all = true;
	
	for j in 0..group_num {
		group_delevered.push((0, j));
	}

	eprintln!("step,group,score,delevered,total_score,total_delevered,total_order,dist,time");
	for i in 0..input.T {
		// 行動決定前に注文が入る
		let order = input.order[i];
		if order.1 != input.V {
			ordered_time_list[order.1].push(i);
			total_order += 1;
			if total_order==2750 {center = i;}
		}
		// 行動
		if i!=next_time{
			if i<=wait_time{
				print_stay();
			}
		}
		else{			
			let mut set = vec![HashSet::new(); group_num];
			let mut visited_node = vec![false; input.V];
			let mut delevered = 0;
			let mut cur_time = i;
			let mut score = 0;

			let mut turn = group_delevered[idx%group_num].1;
			// 未配達の品物に関して、グループを作成
			for j in 1..input.V {
				if ordered_time_list[j].len()!=0 {
					set[group[j]].insert(j);
				}
			}

			if set[turn].len()==0 || (set[turn].len()<=2 && i<9500) // 注文がほぼないときは処理をしない
			{ 
				next_time = i + ITEM_STEP;
				wait_time = i + ITEM_STEP;
				print_stay();
				continue;
			}

			// let (prev_dist, tmp_route) = calc_TSP(&set[turn], &input);
			let (prev_dist, tmp_route) = clean_unused_nodes_TSP(&set[turn], &input, &route_list[turn]);
			let mut tmp_nroute = vec![];
			if set[turn].len()>2 {tmp_nroute = improve_TSP(tmp_route, &mut input, i, &ordered_time_list);}
			else {tmp_nroute = tmp_route;}
			let after_dist = route_dist(&tmp_nroute, &input);
			next_time = i + after_dist;
			// eprintln!("step {} size {} turn {} prev_dist {} after_dist {} total_order {}", i, set[turn].len(), 
			//            turn, prev_dist, after_dist, total_order);

			// 最後はまとめられる分をまとめて配送
			if i > 9500 && next_time < input.T && try_delever_all {
				let mut last_num = 1;
				let mut last_set = HashSet::new();
				for &j in &set[turn]{
					last_set.insert(j);
				}
				set[turn] = HashSet::new();
				for j in idx+1..idx+group_num {
					let next_turn = group_delevered[j%group_num].1;
					if set[next_turn].len() > 0 {last_num+=1;}
					for &k in &set[next_turn]{
						last_set.insert(k);
					}
					set[next_turn] = HashSet::new();
					let (next_dist, next_route) = calc_TSP(&last_set, &input);
					let next_limit = i + next_dist;
					if next_limit>=input.T+100 {break;}
				}
				let (mut last_prev_dist, last_route) = calc_TSP(&last_set, &input);
				let mut last_nroute = vec![];
				if last_set.len() > 2 {last_nroute = improve_TSP(last_route, &mut input, 10000, &ordered_time_list);}
				else {last_nroute = last_route;}
				let last_after_dist = route_dist(&last_nroute, &input);
				next_time = i + last_after_dist;
				// eprintln!("step {} size {} num {} last_prev_dist {} last_after_dist {}", i, last_set.len(), 
				//           last_num, last_prev_dist, last_after_dist);
				delever_items(&last_nroute, &input, i, &mut ordered_time_list, &mut delevered, 
				              &mut cur_time, &mut visited_node, &mut score);
				total_score += score;
				// eprintln!("delevered {} total_score {} percentage {}", delevered, total_score,
				//           score as f64 /delevered as f64);
				total_delevered += delevered;
				eprintln!("{}, {}, {}, {}, {}, {}, {}, {}, {}", 
			           i, turn, score, delevered, total_score, total_delevered, total_order, last_after_dist, get_time());
				idx += 1;
				continue;
			}

			delever_items(&tmp_nroute, &input, i, &mut ordered_time_list, &mut delevered, 
			              &mut cur_time, &mut visited_node, &mut score);
			total_score += score;

			// eprintln!("delevered {} total_score {} percentage {}", delevered, total_score, 
			//            score as f64 /delevered as f64);
			// eprintln!("efficiency {} cur_time {} visited_num {}",
			//            delevered as f64 / after_dist as f64, cur_time, visited_num);

			total_delevered += delevered;
			eprintln!("{}, {}, {}, {}, {}, {}, {}, {}, {}", 
			           i, turn, score, delevered, total_score, total_delevered, total_order, after_dist, get_time());
			for j in 0..group_num {
				let id = group_delevered[j].1;
				if id==turn {group_delevered[j].0 += delevered;}
			}
			idx = (idx+1)%group_num;
		}
	}
	// eprintln!("V {} E {}", input.V, input.E);
	// eprintln!("order {} total_delevered {}",total_order, total_delevered);
    // eprintln!("score {} percengage {} center {}", total_score, total_score as f64 / total_order as f64, center);
}

fn read_inputs() -> Input {
	let (V,E) = read!(usize,usize);
	let uvd = read!([usize];E);
	let T = read!(usize);
	let mut order = vec![(V,V);T];
	for i in 0..T {
		let N = read!(usize);
		if N==0 {continue;}
		let info = read!(usize,usize);
		order[i] = (info.0-1, info.1-1);
	}
	let mut edge = vec![vec![];V];
	for i in 0..E {
		let s = uvd[i][0]-1;
		let t = uvd[i][1]-1;
		let d = uvd[i][2];
		edge[s].push((t,d));
		edge[t].push((s,d));
	}
	let input = Input::new(V,E,T,edge,order);
	input
}

fn run() {
	let mut input = read_inputs();
	input.init();
	// input.print_closest();
    solve(&mut input);
}


Measured memory_bytes: 12668