#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]



#[allow(unused_macros)]
macro_rules! invec {
    ( $ t : ty ) => {{
        let mut s = String::new();
        match std::io::stdin().read_line(&mut s) {
            Ok(0) => Vec::<$t>::new(),
            Ok(n) => s
                .trim()
                .split_whitespace()
                .map(|s| s.parse::<$t>().unwrap())
                .collect::<Vec<$t>>(),
            Err(_) => Vec::<$t>::new(),
        }
    }};
}

#[allow(unused_macros)]
macro_rules! get {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              get!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              get!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty ;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty ;; $n:expr) => {
          (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
      };
}

#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [$t:tt]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

 
#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    //($arg:expr) => (println!("{:?}",$arg));
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
}
 
 
#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}

use std::cmp;
use std::collections::HashMap;
use std::collections::BinaryHeap;
use std::io::{self, Write};

#[allow(dead_code)]
static INF_I64 :i64 = 9223372036854775807;
#[allow(dead_code)]
static INF_I32 : i32 = 2147483647;
#[allow(dead_code)]
static INF_USIZE : usize = 7446744073709551615;



fn get_package(time:usize, bflag : bool)->Vec<(usize,usize,usize)>{
    let mut info = vec![];
    let a = get!(usize);
    if a == 0 {
        //info.push(vec![(0,500)]);
        //continue;
        info.push((10000000,0,0));
        
    }
    else{
        let items = get!(usize,usize;a);
        for j in 0..items.len(){
            let tmp = items[j];
            info.push((time,tmp.0-1,tmp.1-1));
        }
    }

    if bflag{
        let b = get!(usize);
        for _ in 0..b{
           let _ = get!(usize);
        }
    }
    return info;

}
fn post(ret:&str,bflag:bool)->bool{
    
    println!("{}",ret);
    io::stdout().flush().unwrap();
    if bflag {
        let verdict = get!(String);
        if verdict == "NG"{
            return false;
        }
        let c = get!(usize);
        for _ in 0..c{
           let _ = get!(usize);
        }
        
    }
    return true;

}




fn main() {


    
    let bflag = true;
    let (n,m) = get!(usize,usize);
    //mydbg!(n,m);
    
    
    let mut edges = get!(usize,usize,usize;m);
    if bflag {
        //let f = get!(i32;n);
        let f = invec!(usize);
    }
    let tmax = get!(usize);
    
    let mut info:Vec<(usize,usize,usize)> = vec![];


    let mut graph = vec![vec![];n];
    
    for i in 0..m{
        let e = edges[i];
        graph[e.0-1].push(e.1-1);
        graph[e.1-1].push(e.0-1);
    }

    // for i in 0..tmax{
    //     let a = get!(usize);
    //     if a == 0 {
    //         //info.push(vec![(0,500)]);
    //         continue;
    //     }
    //     let items = get!(usize,usize;a);
    //     for j in 0..items.len(){
    //         let tmp = items[j];
    //         info.push((i,tmp.0,tmp.1));
    //     }
        
    // }
    
 
 
    // for i in 0..info.len(){
    //     let a= info[i];
    //     info[i]  = (a.0,a.1-1,a.2-1);
    // }
    

    let mut dp = vec![vec![INF_USIZE;n];n];

    for i in 0..m{
        let e = edges[i];
        dp[e.0-1][e.1-1] = e.2;
        dp[e.1-1][e.0-1] = e.2;
        dp[e.0-1][e.0-1] = 0;
        dp[e.1-1][e.1-1] = 0;
    }

    
    let mut next = vec![vec![n;n];n];
    for i in 0..n{
        for j in 0..n{
            next[i][j] = j;
        }
    }

    for k in 0..n{
        for i in 0..n{
            for j in 0..n{
                let tmp = dp[i][k]+dp[k][j];
                if tmp < dp[i][j]{
                    dp[i][j] = tmp;
                    next[i][j] = next[i][k];
                }
            }
        }
    }


    let mut maxcost = 0;
    for i in 0..n{
        maxcost = cmp::max(maxcost, dp[i][0]);
    }
    mydbg!(maxcost);
    //mydbg!(dp);
    
    let mut cur = 0;
    let mut ans:Vec<i32> = vec![];
    let mut time = 0;
    let mut used = vec![0;info.len()];
    mydbg!(used.len(),info.len(),next.len(),dp.len());
    let mut package = vec![];
    let mut present = 0;
    
    let mut now = 1;
    let tmp = get_package(0,bflag);
    for i in 0..tmp.len(){
        info.push(tmp[i]);
    }


    #[derive(Debug)]
    struct Node {
        keiro: Vec<usize>,
        score:  i64,
        time : usize,
        used : Vec<usize>,
    }

    impl PartialEq for Node {
        fn eq(&self, other: &Self) -> bool {
            self.score == other.score
        }
    }
    impl Eq for Node {}
    impl PartialOrd for Node {
        fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
            Some(self.cmp(&other))
        }
    }
    impl Ord for Node {
        fn cmp(&self, other: &Self) -> std::cmp::Ordering {
            self.score.cmp(&other.score)
        }
    }

            
    'outer2 :loop{
        if time >= tmax{
            break;
        }
        
        // for i in cur..info.len(){
        //     if info[i].0 <= time{
        //         package.push(info[i]);
        //     }
        //     else {
        //         cur = i;
        //         break;
        //     }
        // }
        for i in 0..info.len(){
            if info[i].0 == 10000000{
                continue;
            }
            else if info[i].0 == 10000001{
                break;
            }
            package.push(info[i]);
        }
        info =vec![];

        if package.len() == 0 {
            time += 1;
            //ans.push(-1);
            let tmp = post(&"-1",bflag);
            now += 1;
            if now > tmax {
                return;
            }
            if tmp == false {return};
            let tmp = get_package(now,bflag);
            for i in 0..tmp.len(){
                info.push(tmp[i]);
            }
            continue;
        }

        let mut pcount = package.len() as i32;

        //mydbg!(package);
        //mydbg!(package.len());
        //package.reverse();

        //let mut used = vec![0;n];
        
        
        mydbg!(package.len());

        loop{
            let mut path = vec![];
            
            if false {

                
                package.sort_by(|x,y|{
                    if dp[present][x.2] > dp[present][y.2]{
                        cmp::Ordering::Less
                    }
                    else if dp[present][x.2] == dp[present][y.2]{
                        return y.0.cmp(&x.0);
                    }
                    else{
                        cmp::Ordering::Greater
                    }
                });
            }

            if false{
                package.sort_by(|x,y|{
                    let scorex =tmax.pow(2)-  (now + dp[present][x.2] - x.0).pow(2);
                    let scorey =tmax.pow(2)-  (now + dp[present][y.2] - y.0).pow(2);
                    if scorex > scorey{
                        cmp::Ordering::Greater
                    }
                    else if scorex==scorey{
                        return y.0.cmp(&x.0);
                    }
                    else{
                        cmp::Ordering::Less
                    }
                });
            }

            

            if true && (present == 0 || package.len()  % 16 == 0){

                let width = 13;
                //let mut max_shop = package.len() as i32;
                let mut max_shop = 90;
                let max_depth = 20;
                let mut depth = 0;


                if true{
                    package.sort_by(|x,y|{
                        if dp[present][x.2] > dp[present][y.2]{
                            cmp::Ordering::Greater
                        }
                        else if dp[present][x.2] == dp[present][y.2]{
                            return x.0.cmp(&y.0);
                        }
                        else{
                            cmp::Ordering::Less
                        }
                    });
                }

                if false{
                    package.sort_by(|x,y|{
                        let scorex =tmax.pow(2)-  (now + dp[present][x.2] - x.0).pow(2);
                        let scorey =tmax.pow(2)-  (now + dp[present][y.2] - y.0).pow(2);
                        if scorex > scorey{
                            cmp::Ordering::Less
                        }
                        else if scorex==scorey{
                            return x.0.cmp(&y.0);
                        }
                        else{
                            cmp::Ordering::Greater
                        }
                    });
                }

                let mut kouho   = BinaryHeap::new();
                let mut good_kouho   = BinaryHeap::new();
    
                kouho.push(Node {
                    keiro: vec![],
                    used : vec![0;package.len()],
                    score:  0,
                    time : now,
                });
    
    
                
    
    
                
    
                while !kouho.is_empty() || depth < max_depth{
                    depth += 1;
                    //max_shop  = std::cmp::max(max_shop - 20 ,1);
                    let mut next_kouho = BinaryHeap::new();
                    //mydbg!(kouho);
                    for _ in 0..std::cmp::min(width, kouho.len()) {
                        let node = kouho.pop().unwrap();
                        let nowposition = if node.keiro .len() > 0 { package[node.keiro[node.keiro.len()-1]].2 } else {present};
                        
                        let mut count = 0;
                        for p in 0..std::cmp::min(max_shop as usize , package.len()){
                        //for p in 0..package.len(){
                            if node.used[p] != 0 {
                                continue;
                            }
                            
                            if count > max_shop {break};
                            count+=1;
    
                            
                            let package1 = package[p];
                            
                            
                            
                            let mut next_score = node.score;
                            let cost = dp[nowposition][package1.2];
                            let mut next_used = node.used.clone();
    
                            //next_score += tmax.pow(2) as i64  - (node.time + cost - package1.0).pow(2) as i64;
                            next_score += tmax as i64 - cost  as i64;
                            next_used[p] = 1;
                            
                            
                            let mut next_keiro = node.keiro.clone();
                            next_keiro.push(p);
                            next_kouho.push(Node{
                                keiro : next_keiro,
                                score : next_score,
                                time : node.time + cost,
                                used : next_used,
                            });
    
    
                        }
                    }
                    kouho = next_kouho;
                    if !kouho.is_empty(){
                        let k = kouho.pop().unwrap();
                        good_kouho.push(Node{
                            keiro : k.keiro.clone(),
                            score : k.score.clone(),
                            time : k.time.clone(),
                            used : k.used.clone(),
                        });
                        kouho.push(Node{
                            keiro : k.keiro,
                            score : k.score,
                            time : k.time,
                            used : k.used,
                        });
                    }
                    
                    
    
                }

                
    
                let k = good_kouho.pop().unwrap();
                

                let mut tmp = vec![];
                for i in 0..k.keiro.len(){
                    tmp.push(package[k.keiro[i]]);
                }
                
                //mydbg!(k.keiro);

                for i in 0..package.len(){
                    if k.used[i] == 0{
                        tmp.push(package[i]);
                    }
                }
                
                tmp.reverse();
                
                
                package = tmp;
    
            }
            

            let mut tmp = package[package.len()-1];
       




            //mydbg!(tmp);
            let g = tmp.2;
            let mut target = present;
            //let g = 0;
            //let mut target = tmp.2;
            loop{
                target = next[target][g];
                path.push(target);
                if target == g{
                    break;
                }
            }

            //let mut b = present;
            'outer : for i in 0..path.len(){
                //mydbg!(b,*item,dp[b][*item]);
                let item = path[i];
                for _ in 0..dp[present][item]{
                    //ans.push(item as i32+1);
                    let tmp = post(&(item as i32+1).to_string(),bflag);
                    now += 1;
                    if now > tmax {
                        return;
                    }
                    if tmp == false{return};
                    let tmp = get_package(now,bflag);
                    for i in 0..tmp.len(){
                        info.push(tmp[i]);
                    }
                }
                present = item;
                //if i != path.len()-1 &&  dp[present][0] < dp[present][path[i+1]]{
                if i != path.len()-1{
                    if  (package.len() as i32) < std::cmp::max(pcount -10,1)  && ((dp[present][0] < maxcost / 8 && info.len() > n/9 ) || 
                       (dp[present][0] as f32 * 0.8 < dp[present][path[i+1]] as f32 && info.len() > 5 )){ // 463168586749 good n/14
                    //if (package.len() as i32) < std::cmp::max(pcount -5,1) &&  ( dp[present][0] < 5 || package.len() < 30) &&  info.len() > 1{
                    
                        //if (dp[present][0] < maxcost / 8 && info.len() > n/9 )|| (dp[present][0] < maxcost / 3  && info.len() > n/2) { //463030657950
                    //if false {
                        mydbg!("戻る");
                        loop{
                            let t = next[present][0];
                            for _ in 0..dp[present][t]{
                                //ans.push(t as i32+1);
                                let tmp = post(&(t as i32+1).to_string(),bflag);
                                now += 1;
                                if now > tmax {
                                    return;
                                }
                                if tmp == false{return};
                                let tmp = get_package(now,bflag);
                                for i in 0..tmp.len(){
                                    info.push(tmp[i]);
                                }
                            }
                            present = t;
                            if present == 0{
                                break;
                            }
                        }
                        //break 'outer;
                        continue 'outer2;
                    }
                }
            }

            package.pop();
            
            //mydbg!(package.len());
            if false  && present == 0 {
                break;
            }
            if package.len() == 0 {
            //if true { //一回配達するごとに絶対もどる
                //mydbg!("戻る2");
                loop{
                    let t = next[present][0];
                    for _ in 0..dp[present][t]{
                        //ans.push(t as i32+1);
                        let tmp = post(&(t as i32+1).to_string(),bflag);
                        now += 1;
                        if now > tmax {
                            return;
                        }
                        if tmp == false{return};
                        let tmp = get_package(now,bflag);
                        for i in 0..tmp.len(){
                            info.push(tmp[i]);
                        }
                    }
                    present = t;
                    if present == 0{
                        break;
                    }
                }
                break;
            }

            //if dp[present][0] < maxcost / 10  && dp[present][0]*2 < dp[present][package[package.len()-1].2]{
            //if (dp[present][0] < 10 && info.len() > 10 ) { //462982464483 good
            //if (dp[present][0] < 9 && info.len() > 25 ) || (dp[present][0] < 30 && info.len()> 120){ // 463069461709 good
            //if (dp[present][0] < maxcost / 8 && info.len() > 26 )|| (dp[present][0] < 30 && info.len()> 120) { //463069461709 good
            //if (dp[present][0] < maxcost / 8 && info.len() > 26 )|| (dp[present][0] < maxcost / 3  && info.len()> 90) { //463120523294 good
            //if (dp[present][0] < maxcost / 8 && info.len() > 26 )|| (dp[present][0] < maxcost / 3  && info.len()> 88) { //463121984399 good
            //if (dp[present][0] < maxcost / 8 && info.len() > n/9 )|| (dp[present][0] < maxcost / 3  && info.len() > n/2) { //463030657950
            //if (dp[present][0] < maxcost / 8 && info.len() > n/8 ) || (dp[present][0] < maxcost / 3  && info.len() > n/2) { //463030657950
            
            if  (package.len() as i32) < std::cmp::max(pcount -20,1)  &&
            ((tmax as f32  * 0.945 > now as f32) && (tmax as f32  * 0.96 < now as f32) ) && ( info.len() > 1 )
            || (tmax as f32  * 0.94 < now as f32) && (dp[present][0] < maxcost / 8 && info.len() > n/8 ) || (dp[present][0] < maxcost / 3  && info.len() > n/2) { //463030657950
            
            //if dp[present][0] < maxcost / 7 && info.len() > 13 { //462982464483 good
            //if dp[present][0] < 30 { //47137482026
            //if dp[present][0] < 60 { // 47333223951
            //if dp[present][0] < 50 { // 47137482026
            //if dp[present][0] < 70 { // 47333223951
            //if dp[present][0] < 90 { // 47333223951
            
            //if (package.len() as i32) < std::cmp::max(pcount -20,1) &&  ( dp[present][0] < 5 || package.len() < 100) &&  info.len() > 10{
            //if false {
                //mydbg!("戻る3");
                loop{
                    let t = next[present][0];
                    for _ in 0..dp[present][t]{
                        //ans.push(t as i32+1);
                        let tmp = post(&(t as i32+1).to_string(),bflag);
                        now += 1;
                        if now > tmax {
                            return;
                        }
                        if tmp == false{return};
                        let tmp = get_package(now,bflag);
                        for i in 0..tmp.len(){
                            info.push(tmp[i]);
                        }
                    }
                    present = t;
                    if present == 0{
                        break;
                    }
                }
                time = ans.len();
                break;
            }
            
            
            time = ans.len();
        }

        time = ans.len();

    }

 
 



}



Measured memory_bytes: 33072