// Practice Hitachi Hokudai Labo & Hokkaido University Contest 2019-1
// author: Leonardone @ NEETSDKASU

macro_rules! ewriteln {
    ($fmt:expr)  => {{
        use std::io::Write;
        writeln!(&mut std::io::stderr(), $fmt).unwrap();
    }};
    ($fmt:expr, $($arg:tt)*) => {{
        use std::io::Write;
        writeln!(&mut std::io::stderr(), $fmt, $($arg)*).unwrap();
    }};
}

fn main() {
    let start_time = std::time::SystemTime::now();
    let time_limit = std::time::Duration::from_millis(29500);

    let io = StandardIO::new();
    let mut io = io.get_io();

    let problem = Problem::read(&mut io);

    if cfg!(debug_assertions) {
        ewriteln!("vertex_count: {}", problem.vertex_count);
        let far_from1 = problem.fw_table[1][2..]
            .iter()
            .enumerate()
            .max_by(|u, v| u.1.distance.cmp(&v.1.distance))
            .unwrap();
        ewriteln!(
            "far from 1: id({}), distance({})",
            far_from1.0 + 2,
            far_from1.1.distance
        );
        let most_far = problem.fw_table[1..]
            .iter()
            .enumerate()
            .map(|(i, row)| {
                let (j, conn) = row[1..]
                    .iter()
                    .enumerate()
                    .max_by(|u, v| u.1.distance.cmp(&v.1.distance))
                    .unwrap();
                (i, j, conn)
            })
            .max_by(|u, v| u.2.distance.cmp(&v.2.distance))
            .unwrap();
        ewriteln!(
            "most far pair: id({}) id({}) distance({})",
            most_far.0 + 1,
            most_far.1 + 1,
            most_far.2.distance
        );
    }

    if problem.is_interactive {
        let mut solver = SolverB::new(start_time, time_limit, &problem);
        let mut achived_orders = vec![];
        for time in 0..problem.time_max {
            let new_orders = read_new_orders(&mut io);
            let put_orders = read_put_orders(&mut io);
            let cmd = solver.get_command(time, &new_orders, &put_orders, &achived_orders);
            io.println(cmd);
            if io.gets() != "OK" {
                break;
            }
            achived_orders = read_achived_orders(&mut io);
        }
    } else {
        let solver = SolverA::new(start_time, time_limit, &problem);
        let mut new_orders = vec![];
        for _ in 0..problem.time_max {
            new_orders.push(read_new_orders(&mut io));
        }
        let commands = solver.get_commands(&new_orders);
        for cmd in commands.iter() {
            io.println(cmd);
        }
    }

    ewriteln!("solution time: {:?}", start_time.elapsed().unwrap());
}

type OrderID = usize;
type VertexID = usize;
type Distance = i32;
const DISATANCE_INFINITY: Distance = std::i32::MAX / 2;

struct SolverA<'a> {
    start_time: std::time::SystemTime,
    time_limit: std::time::Duration,
    problem: &'a Problem,
}

impl<'a> SolverA<'a> {
    fn new(stime: std::time::SystemTime, limit: std::time::Duration, prob: &'a Problem) -> Self {
        SolverA {
            start_time: stime,
            time_limit: limit,
            problem: prob,
        }
    }
    fn get_commands(&self, new_orders: &[Vec<Order>]) -> Vec<Command> {
        let problem = &self.problem;
        let mut solver = SolverB::new(self.start_time, self.time_limit, problem);
        let mut commands = Vec::with_capacity(problem.time_max);
        let mut reserve_orders = vec![];
        let mut put_orders = vec![];
        let mut achived_orders = vec![];
        let mut carring_orders = std::collections::HashMap::new();
        let mut car_pos = 1;
        let mut car_movings = 0;
        for (time, nos) in new_orders.iter().enumerate() {
            reserve_orders.extend_from_slice(nos);
            if car_pos == 1 && car_movings == 0 {
                for order in reserve_orders.iter() {
                    carring_orders
                        .entry(order.destination)
                        .or_insert_with(Vec::new)
                        .push(order.id);
                    put_orders.push(order.id);
                }
                reserve_orders.clear();
            }
            let cmd = solver.get_command(time, nos, &put_orders, &achived_orders);
            put_orders.clear();
            achived_orders.clear();
            if let Command::Move(id) = cmd {
                car_movings += 1;
                if problem.fw_table[car_pos][id].distance == car_movings {
                    car_pos = id;
                    car_movings = 0;
                    if let Some(orders) = carring_orders.remove(&id) {
                        achived_orders.extend_from_slice(&orders);
                    }
                }
            }
            commands.push(cmd);
        }
        /* for debug */
        {
            let n: usize = new_orders.iter().map(Vec::len).sum();
            ewriteln!("all orders: {}", n);
            let c: usize = carring_orders.iter().map(|v| v.1.len()).sum();
            ewriteln!("carring orders: {}", c);
            let r = reserve_orders.len();
            ewriteln!("reserved order: {}", r);
            let a = n - c - r;
            ewriteln!("achived order: {}", a);
        }
        commands
    }
}

struct SolverB<'a> {
    _start_time: std::time::SystemTime,
    _time_limit: std::time::Duration,
    problem: &'a Problem,
    commands: Vec<Connection>,
    command_pos: usize,
    orders: std::collections::BTreeMap<VertexID, i32>,
    order_table: std::collections::HashMap<OrderID, VertexID>,
}

impl<'a> SolverB<'a> {
    fn new(stime: std::time::SystemTime, limit: std::time::Duration, prob: &'a Problem) -> Self {
        SolverB::<'a> {
            _start_time: stime,
            _time_limit: limit,
            problem: prob,
            commands: vec![],
            command_pos: 0,
            orders: std::collections::BTreeMap::new(),
            order_table: std::collections::HashMap::new(),
        }
    }
    fn get_command(
        &mut self,
        time: usize,
        new_orders: &[Order],
        put_orders: &[OrderID],
        achived_orders: &[OrderID],
    ) -> Command {
        self.update_orders(new_orders, put_orders, achived_orders);
        if let Some(id) = self.next_move_to() {
            return Command::Move(id);
        }
        if self.orders.is_empty() {
            return Command::Stay;
        }
        self.make_commands(time);
        self.next_move_to().map_or(Command::Stay, Command::Move)
    }
    fn update_orders(
        &mut self,
        new_orders: &[Order],
        put_orders: &[OrderID],
        achived_orders: &[OrderID],
    ) {
        let orders = &mut self.orders;
        let order_table = &mut self.order_table;
        for order in new_orders {
            order_table.insert(order.id, order.destination);
        }
        for order_id in achived_orders.iter() {
            let vertex_id = order_table.get(order_id).unwrap();
            if let std::collections::btree_map::Entry::Occupied(mut oe) = orders.entry(*vertex_id) {
                *oe.get_mut() -= 1;
                if *oe.get() == 0 {
                    oe.remove();
                }
            }
        }
        for order_id in put_orders.iter() {
            let vertex_id = order_table.get(order_id).unwrap();
            *orders.entry(*vertex_id).or_insert(0) += 1;
        }
    }
    fn next_move_to(&mut self) -> Option<VertexID> {
        self.commands
            .get_mut(self.command_pos)
            .map(|conn| {
                if conn.distance == 0 {
                    None
                } else {
                    conn.distance -= 1;
                    Some(conn.vertex_id)
                }
            })
            .and_then(|id| {
                id.or_else(|| {
                    self.command_pos += 1;
                    self.next_move_to()
                })
            })
    }
    fn make_commands(&mut self, time: usize) {
        let mut ids = vec![1, 1, 1, 1, 1, 1, 1];
        ids.extend_from_slice(&self.orders.keys().cloned().collect::<Vec<_>>());
        ids.push(1);
        self.optimize_path(&mut ids);
        ids.dedup();
        {
            let mut best_lp = 0;
            let mut best_rp = ids.len() - 1;
            let mut best_perf = 0.0;
            let mut lp = 0;
            let mut rp = 1;
            let mut dist = 0;
            let mut count = 0;
            while rp < ids.len() {
                dist += self.problem.fw_table[ids[rp - 1]][ids[rp]].distance;
                count += *self.orders.get(&ids[rp]).unwrap_or(&0);
                if ids[rp] == 1 {
                    let len = rp - lp + 1;
                    if len > 2 {
                        let perf = count as f64 / dist as f64;
                        if perf > best_perf {
                            best_lp = lp;
                            best_rp = rp;
                            best_perf = perf;
                        }
                    }
                    dist = 0;
                    count = 0;
                    lp = rp;
                }
                rp += 1;
            }
            ids = ids[best_lp..best_rp + 1].to_vec();
        }
        self.build_commands(&ids, ids.len());
        let total_time = time
            + self
                .commands
                .iter()
                .map(|conn| conn.distance as usize)
                .sum::<usize>();
        if total_time >= self.problem.time_max {
            ewriteln!("time over");
            self.make_nonback_commands();
        }
        if cfg!(debug_assertions) {
            let fw = &self.problem.fw_table;
            let vc = ids.len() - 2;
            let mut dist = 0;
            for i in 1..ids.len() {
                dist += fw[ids[i - 1]][ids[i]].distance;
            }
            assert!(time + dist as usize == total_time);
            let oc: i32 = ids[1..ids.len() - 1]
                .iter()
                .filter(|i| **i > 1)
                .map(|i| *self.orders.get(i).unwrap())
                .sum();
            let shop = self
                .commands
                .iter()
                .filter(|conn| conn.vertex_id == 1)
                .count();
            ewriteln!(
                concat!(
                    "time: {}, ",
                    "vertex: {}, ",
                    "order: {}, ",
                    "dist: {}, ",
                    "vert_rate: {:.3}, ",
                    "deli_rate: {:.3}, ",
                    "shop: {}"
                ),
                time,
                vc,
                oc,
                dist,
                vc as f64 / self.problem.vertex_count as f64,
                oc as f64 / dist as f64,
                shop
            );
        }
    }
    fn make_nonback_commands(&mut self) {
        let mut ids = vec![1];
        ids.extend_from_slice(&self.orders.keys().cloned().collect::<Vec<_>>());
        ids.push(0);
        for _ in 0..5 {
            self.optimize_path(&mut ids);
        }
        self.build_commands(&ids, ids.len() - 1);
    }
    fn build_commands(&mut self, ids: &[VertexID], end: usize) {
        self.commands.clear();
        self.command_pos = 0;
        for i in 0..end - 1 {
            let path = self.problem.get_path(ids[i], ids[i + 1]);
            for conn in path.iter() {
                self.commands.push(conn.clone());
            }
        }
    }
    fn optimize_path(&self, ids: &mut [VertexID]) {
        let fw = &self.problem.fw_table;

   for i in 1..ids.len() - 2 {
            let mut best = i;
            for j in i + 1..ids.len() - 1 {
                if fw[ids[i - 1]][ids[j]].distance < fw[ids[i - 1]][ids[best]].distance {
                    best = j;
                }
            }
            if best != i {
                ids.swap(i, best);
            }
        }
        for _ in 0..ids.len() * 2 {
            for lp in 1..ids.len() - 2 {
                for rp in lp + 1..ids.len() - 1 {
                    let lid0 = ids[lp - 1];
                    let lid1 = ids[lp];
                    let rid0 = ids[rp];
                    let rid1 = ids[rp + 1];
                    let bef = fw[lid0][lid1].distance + fw[rid1][rid0].distance;
                    let aft = fw[lid0][rid0].distance + fw[rid1][lid1].distance;
                    if aft - bef > 0 {
                        continue;
                    }
                    ids[lp..rp + 1].reverse();
                }
            }
        }
    }
}

enum Command {
    Move(VertexID),
    Stay,
}

impl std::fmt::Display for Command {
    fn fmt(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
        match *self {
            Command::Move(v) => v.fmt(formatter),
            Command::Stay => "-1".fmt(formatter),
        }
    }
}

#[derive(Clone)]
struct Connection {
    vertex_id: VertexID,
    distance: Distance,
}

impl Connection {
    fn new(i: VertexID, d: Distance) -> Self {
        Connection {
            vertex_id: i,
            distance: d,
        }
    }
}

struct Problem {
    vertex_count: usize,
    _frequency: Vec<usize>,
    time_max: usize,
    is_interactive: bool,
    fw_table: Vec<Vec<Connection>>,
}

impl Problem {
    fn read(io: &mut IO) -> Self {
        let (vc, ec) = io.get2();
        let mut fw = vec![];
        for i in 0..vc + 1 {
            let mut tmp = vec![];
            for j in 0..vc + 1 {
                tmp.push(Connection::new(j, DISATANCE_INFINITY));
            }
            tmp[i].distance = 0;
            fw.push(tmp);
        }
        fw[1][1].distance = DISATANCE_INFINITY;
        for _ in 0..ec {
            let (u, v, d): (VertexID, VertexID, Distance) = io.get3();
            fw[u][v] = Connection::new(v, d);
            fw[v][u] = Connection::new(u, d);
        }
        for i in 0..vc + 1 {
            for j in 0..vc + 1 {
                for k in 0..vc + 1 {
                    let dist = fw[j][i].distance + fw[i][k].distance;
                    let mut tmp = &mut fw[j][k];
                    if tmp.distance > dist {
                        tmp.vertex_id = i;
                        tmp.distance = dist;
                    }
                }
            }
        }
        let freq = io.get_vec();
        let interacive = freq[0] == 0;
        let t_max = if !interacive { freq[0] } else { io.get() };
        Problem {
            vertex_count: vc,
            _frequency: freq,
            time_max: t_max,
            is_interactive: interacive,
            fw_table: fw,
        }
    }
    fn get_path(&self, start_id: VertexID, goal_id: VertexID) -> Vec<Connection> {
        let fw = &self.fw_table;
        let mut path = vec![];
        let mut stack = vec![];
        stack.push((start_id, goal_id));
        while let Some((s, g)) = stack.pop() {
            let conn = &fw[s][g];
            if conn.vertex_id == g {
                path.push(conn.clone());
                continue;
            }
            stack.push((conn.vertex_id, g));
            stack.push((s, conn.vertex_id));
        }
        path
    }
}

#[derive(Clone)]
struct Order {
    id: OrderID,
    destination: VertexID,
}

impl Order {
    fn new(i: OrderID, d: VertexID) -> Self {
        Order {
            id: i,
            destination: d,
        }
    }
}

fn read_new_orders(io: &mut IO) -> Vec<Order> {
    let mut orders = vec![];
    let n = io.get();
    for _ in 0..n {
        let (i, d) = io.get2();
        orders.push(Order::new(i, d));
    }
    orders
}

fn read_put_orders(io: &mut IO) -> Vec<OrderID> {
    let mut orders = vec![];
    let n = io.get();
    for _ in 0..n {
        orders.push(io.get());
    }
    orders
}

fn read_achived_orders(io: &mut IO) -> Vec<OrderID> {
    let mut orders = vec![];
    let n = io.get();
    for _ in 0..n {
        orders.push(io.get());
    }
    orders
}

struct StandardIO {
    stdin: std::io::Stdin,
    stdout: std::io::Stdout,
}

struct IO<'a> {
    stdin: std::io::StdinLock<'a>,
    stdout: std::io::StdoutLock<'a>,
}

impl StandardIO {
    fn new() -> Self {
        StandardIO {
            stdin: std::io::stdin(),
            stdout: std::io::stdout(),
        }
    }
    fn get_io(&self) -> IO {
        IO {
            stdin: self.stdin.lock(),
            stdout: self.stdout.lock(),
        }
    }
}

impl<'a> IO<'a> {
    fn get_line(&mut self) -> String {
        let mut line = String::new();
        std::io::BufRead::read_line(&mut self.stdin, &mut line).unwrap();
        line
    }
    fn gets(&mut self) -> String {
        self.get_line().trim().to_string()
    }
    fn get<A>(&mut self) -> A
    where
        A: std::str::FromStr,
        A::Err: std::fmt::Debug,
    {
        self.get_line().trim().parse().unwrap()
    }
    fn get2<A, B>(&mut self) -> (A, B)
    where
        A: std::str::FromStr,
        B: std::str::FromStr,
        A::Err: std::fmt::Debug,
        B::Err: std::fmt::Debug,
    {
        let line = self.get_line();
        let mut tokens = line.split_whitespace();
        let a: A = tokens.next().unwrap().parse().unwrap();
        let b: B = tokens.next().unwrap().parse().unwrap();
        (a, b)
    }
    fn get3<A, B, C>(&mut self) -> (A, B, C)
    where
        A: std::str::FromStr,
        B: std::str::FromStr,
        C: std::str::FromStr,
        A::Err: std::fmt::Debug,
        B::Err: std::fmt::Debug,
        C::Err: std::fmt::Debug,
    {
        let line = self.get_line();
        let mut tokens = line.split_whitespace();
        let a: A = tokens.next().unwrap().parse().unwrap();
        let b: B = tokens.next().unwrap().parse().unwrap();
        let c: C = tokens.next().unwrap().parse().unwrap();
        (a, b, c)
    }
    fn get_vec<A>(&mut self) -> Vec<A>
    where
        A: std::str::FromStr,
        A::Err: std::fmt::Debug,
    {
        self.get_line()
            .split_whitespace()
            .map(|v| v.parse().unwrap())
            .collect()
    }
    fn println<A: std::fmt::Display>(&mut self, v: A) {
        use std::io::Write;
        writeln!(&mut self.stdout, "{}", v).unwrap();
        self.stdout.flush().unwrap();
    }
}


Measured memory_bytes: 9420