// SNIPPET hokudai_hitachi2019_1
#[macro_use] mod hokudai_hitachi2019_1 {
use std::collections::BinaryHeap;
use std::cmp;
#[macro_export]
#[cfg(local)]
macro_rules! dbg {
    () => {
        {
            use std::io::{self, Write};
            writeln!(io::stderr(), "{}: dbg", line!()).unwrap();
        }
    };
    ($e: expr) => {
        {
            use std::io::{self, Write};
            let result = $e;
            writeln!(io::stderr(), "{}: {} = {:?}",
                     line!(), stringify!($e), result)
                .unwrap();
            result
        }
    }
}
#[macro_export]
#[cfg(not(local))]
macro_rules! dbg {
    () => {};
    ($e: expr) => { $e }
}
pub struct Env {
    dist: Vec<Vec<u16>>,
    path: Vec<Vec<Vec<usize>>>,
    t_max: usize,
    t_last: usize,
}
#[derive(PartialEq, Eq, Debug)]
struct Node {
    v: usize,
    dist: u16,
    prev: usize
}
impl Node {
    fn new(v: usize, dist: u16, prev: usize) -> Node {
        Node { v: v, dist: dist, prev: prev }
    }
}
impl Ord for Node {
    fn cmp(&self, other: &Node) -> cmp::Ordering {
        other.dist.cmp(&self.dist)
    }
}
impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Node) -> Option<cmp::Ordering> {
        Some(self.cmp(other))
    }
}
impl Env {
    fn dijkstra(
        origin: usize, adj: &[Vec<(usize, u16)>]
    ) -> (Vec<u16>, Vec<Vec<usize>>) {
        const INF: u16 = 16384;
        let v_count = adj.len();
        let mut dists = vec![INF; v_count];
        dists[origin] = 0;
        let mut paths = vec![Vec::new(); v_count];
        let mut queue = BinaryHeap::new();
        for &(v, dist) in &adj[origin] {
            queue.push(Node::new(v, dist, origin));
            dists[v] = dist;
        }
        while let Some(node) = queue.pop() {
            if dists[node.v] < node.dist {
                continue;
            }
            if node.prev != origin {
                let mut path = paths[node.prev].clone();
                path.push(node.prev);
                paths[node.v] = path;
            }
            for &(next, dist) in &adj[node.v] {
                let new_dist = node.dist + dist;
                if dists[next] <= new_dist {
                    continue;
                }
                dists[next] = new_dist;
                queue.push(Node::new(next, new_dist, node.v));
            }
        }
        (dists, paths)
    }
    fn get_dist_and_path(
        adj: &[Vec<(usize, u16)>]
    ) -> (Vec<Vec<u16>>, Vec<Vec<Vec<usize>>>) {
        let v_count = adj.len();
        let mut dist = Vec::new();
        let mut path = Vec::new();
        for v in 0..adj.len() {
            let (d, p) = Env::dijkstra(v, adj);
            dist.push(d);
            path.push(p);
        }
        (dist, path)
    }
    pub fn new(v_count: usize, edges: Vec<(usize, usize, u16)>, t_max: usize) -> Env {
        let mut adj = vec![Vec::new(); v_count];
        for (v1, v2, dist) in edges {
            adj[v1].push((v2, dist));
            adj[v2].push((v1, dist));
        }
        let (dist, path) = Env::get_dist_and_path(&adj);
        Env {
            dist: dist,
            path: path,
            t_max: t_max,
            t_last: t_max / 100 * 95,
        }
    }
    pub fn v_count(&self) -> usize {
        self.dist.len()
    }
    pub fn dist(&self) -> &[Vec<u16>] {
        &self.dist
    }
    pub fn path(&self) -> &[Vec<Vec<usize>>] {
        &self.path
    }
    pub fn t_max(&self) -> usize {
        self.t_max
    }
    pub fn t_last(&self) -> usize {
        self.t_last
    }
    pub fn shop(&self) -> usize {
        0
    }
}
pub mod read {
    use std::io::BufRead;
    pub fn read_v_and_e<R: BufRead>(buf: &mut R) -> (usize, usize) {
        let mut line = String::new();
        buf.read_line(&mut line).unwrap();
        let mut values = line.trim_right().split_whitespace();
        let v: usize = values.next().unwrap().parse().unwrap();
        let e: usize = values.next().unwrap().parse().unwrap();
        (v, e)
    }
    pub fn read_edges<R: BufRead>(buf: &mut R, v: usize, e: usize) -> Vec<(usize, usize, u16)> {
        let mut edges = Vec::new();
        for _ in 0..e {
            let mut line = String::new();
            buf.read_line(&mut line).unwrap();
            let mut values = line.trim_right().split_whitespace();
            let src = values.next().unwrap().parse::<usize>().unwrap() - 1;
            let dest = values.next().unwrap().parse::<usize>().unwrap() - 1;
            let cost: u16 = values.next().unwrap().parse().unwrap();
            edges.push((src, dest, cost));
        }
        edges
    }
    pub fn read_t_max<R: BufRead>(buf: &mut R) -> usize {
        let mut line = String::new();
        buf.read_line(&mut line).unwrap();
        line.trim_right().parse().unwrap()
    }
    pub fn read_order<R: BufRead>(buf: &mut R) -> Vec<usize> {
        let mut header = String::new();
        buf.read_line(&mut header).unwrap();
        let n: usize = header.trim_right().parse().unwrap();
        let mut res = Vec::new();
        for _ in 0..n {
            let mut line = String::new();
            buf.read_line(&mut line).unwrap();
            let mut values = line.trim_right().split_whitespace();
            res.push(values.skip(1).next().unwrap().parse::<usize>().unwrap() - 1);
        }
        res
    }
    pub fn read_frequencies<R: BufRead>(buf: &mut R) -> Vec<u16> {
        let mut line = String::new();
        buf.read_line(&mut line).unwrap();
        let mut values = line.trim_right().split_whitespace();
        values.map(|s| s.parse().unwrap()).collect()
    }
}
}
// SNIPPET iter
#[derive(Clone)]
pub struct StepBy<I> {
    iter: I,
    step: usize,
    first_take: bool
}
impl<I: Iterator> Iterator for StepBy<I> {
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> {
        if self.first_take {
            self.first_take = false;
            self.iter.next()
        } else {
            self.iter.nth(self.step)
        }
    }
}
pub struct Chunks<I: Iterator> {
    iter: I,
    size: usize
}
impl<I: Iterator> Iterator for Chunks<I> {
    type Item = Vec<I::Item>;
    fn next(&mut self) -> Option<Self::Item> {
        let first = self.iter.next();
        if first.is_none() {
            return None;
        }
        let mut chunk = Vec::with_capacity(self.size);
        chunk.push(first.unwrap());
        for _ in 0..self.size-1 {
            match self.iter.next() {
                Some(x) => chunk.push(x),
                None => break
            }
        }
        Some(chunk)
    }
}
#[derive(Clone)]
pub struct LScan<I: Iterator, S: Clone, F: FnMut(&S, I::Item) -> S> {
    iter: I,
    state: Option<S>,
    f: F,
}
impl<I: Iterator, S: Clone, F> Iterator for LScan<I, S, F>
where
    F: FnMut(&S, I::Item) -> S,
{
    type Item = S;
    fn next(&mut self) -> Option<S> {
        if self.state.is_none() {
            return None;
        }
        let state_inner = self.state.take().unwrap();
        if let Some(item) = self.iter.next() {
            self.state = Some((self.f)(&state_inner, item));
        }
        Some(state_inner)
    }
}
pub struct Flatten<I: Iterator>
where
    I::Item: IntoIterator
{
    outer_iter: I,
    inner_iter: Option<<<I as Iterator>::Item as IntoIterator>::IntoIter>
}
impl<I, J> Iterator for Flatten<I>
where
    I: Iterator<Item = J>,
    J: IntoIterator
{
    type Item = <<J as IntoIterator>::IntoIter as Iterator>::Item;
    fn next(&mut self) -> Option<J::Item> {
        loop {
            if let Some(inner_iter) = self.inner_iter.as_mut() {
                if let item@Some(_) = inner_iter.next() {
                    return item
                }
            }
            match self.outer_iter.next() {
                None => return None,
                Some(inner) => self.inner_iter = Some(inner.into_iter())
            }
        }
    }
}
/*
impl<I, J> DoubleEndedIterator for Flatten<I>
where
    I: DoubleEndedIterator,
    J: DoubleEndedIterator,
    I::Item: J {}
*/
pub struct GroupBy<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> {
    cur: Option<(I::Item, K)>,
    iter: I,
    key_fn: F
}
impl<K: Eq, I: Iterator, F: FnMut(&I::Item) -> K> Iterator for GroupBy<K, I, F> {
    type Item = (K, Vec<I::Item>);
    fn next(&mut self) -> Option<(K, Vec<I::Item>)> {
        let cur = self.cur.take();
        cur.map(|(item, key)| {
            let mut group = vec![item];
            loop {
                let next = self.iter.next();
                match next {
                    Some(next_item) => {
                        let next_key = (self.key_fn)(&next_item);
                        if key == next_key {
                            group.push(next_item);
                        } else {
                            self.cur = Some((next_item, next_key));
                            break;
                        }
                    }
                    None => {
                        self.cur = None;
                        break;
                    }
                }
            }
            (key, group)
        })
    }
}
pub struct RunLength<I: Iterator> {
    cur: Option<I::Item>,
    iter: I
}
impl<I: Iterator> Iterator for RunLength<I> where I::Item: Eq {
    type Item = (I::Item, usize);
    fn next(&mut self) -> Option<(I::Item, usize)> {
        let cur = self.cur.take();
        cur.map(|value| {
            let mut length = 1;
            loop {
                let next = self.iter.next();
                match next {
                    Some(next_value) => {
                        if value == next_value {
                            length += 1;
                        } else {
                            self.cur = Some(next_value);
                            break;
                        }
                    }
                    None => {
                        self.cur = None;
                        break;
                    }
                }
            }
            (value, length)
        })
    }
}
pub trait IteratorExt: Iterator {
    fn step_by_(self, step: usize) -> StepBy<Self> where Self: Sized {
        assert_ne!(step, 0);
        StepBy {
            iter: self,
            step: step - 1,
            first_take: true
        }
    }
    fn for_each<F: FnMut(Self::Item)>(self, mut f: F) where Self: Sized {
        for item in self {
            f(item);
        }
    }
    fn chunks(self, size: usize) -> Chunks<Self> where Self: Sized {
        assert!(size > 0);
        Chunks {
            iter: self,
            size: size
        }
    }
    fn lscan<S: Clone, F>(self, state: S, f: F) -> LScan<Self, S, F>
    where
        Self: Sized,
        F: FnMut(&S, Self::Item) -> S,
    {
        LScan {
            iter: self,
            state: Some(state),
            f: f,
        }
    }
    fn get_unique(mut self) -> Option<Self::Item> where Self: Sized, Self::Item: Eq {
        let first_opt = self.next();
        first_opt.and_then(|first| {
            if self.all(|item| item == first) { Some(first) } else { None }
        })
    }
    fn flatten(mut self) -> Flatten<Self> where Self: Sized, Self::Item: IntoIterator {
        let inner_opt = self.next();
        Flatten {
            outer_iter: self,
            inner_iter: inner_opt.map(|inner| inner.into_iter())
        }
    }
    fn group_by<K: Eq, F: FnMut(&Self::Item) -> K>(mut self, mut f: F) -> GroupBy<K, Self, F> where Self: Sized {
        let next = self.next();
        GroupBy {
            cur: next.map(|item| {
                let key = f(&item);
                (item, key)
            }),
            iter: self,
            key_fn: f
        }
    }
    fn run_length(mut self) -> RunLength<Self> where Self: Sized, Self::Item: Eq {
        RunLength {
            cur: self.next(),
            iter: self
        }
    }
    fn join<T: std::fmt::Display>(mut self, sep: T) -> String
    where
        Self: Sized, Self::Item: std::fmt::Display
    {
        let mut result = String::new();
        if let Some(first) = self.next() {
            result.push_str(&format!("{}", first));
        }
        for s in self {
            result.push_str(&format!("{}{}", sep, s));
        }
        result
    }
    fn cat(self) -> String where Self: Sized, Self::Item: std::fmt::Display { self.join("") }
}
impl<I: Iterator> IteratorExt for I {}
pub struct Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    state: Option<T>,
    f: F
}
impl<T, F> Iterator for Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.state.is_none() {
            return None;
        }
        let state_inner = self.state.take().unwrap();
        self.state = (self.f)(&state_inner);
        Some(state_inner)
    }
}
pub fn unfold<T, F>(init: T, f: F) -> Unfold<T, F> where F: FnMut(&T) -> Option<T> {
    Unfold { state: Some(init), f: f }
}
pub struct Iterate<T, F> where F: FnMut(&T) -> T {
    state: T,
    f: F
}
impl<T, F> Iterator for Iterate<T, F> where F: FnMut(&T) -> T {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        use std::mem::swap;
        let mut state = (self.f)(&self.state);
        swap(&mut state, &mut self.state);
        Some(state)
    }
}
pub fn iterate<T, F>(init: T, f: F) -> Iterate<T, F>
where
    F: FnMut(&T) -> T,
{
    Iterate { state: init, f: f }
}
// SNIPPET read
pub trait Readable {
    type Output;
    fn words_count() -> usize;
    fn read_words(words: &[&str]) -> Result<Self::Output, String>;
}
#[macro_export]
macro_rules! readable {
    ( $t:ty, $words_count:expr, |$words:ident| $read_words:expr ) => {
        impl Readable for $t {
            type Output = $t;
            fn words_count() -> usize { $words_count }
            fn read_words($words: &[&str]) -> Result<$t, String> {
                Ok($read_words)
            }
        }
    };
}
readable!((), 1, |_ss| ());
readable!(String, 1, |ss| ss[0].to_string());
impl Readable for char {
    type Output = char;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<char, String> {
        let chars: Vec<char> = words[0].chars().collect();
        if chars.len() == 1 {
            Ok(chars[0])
        } else {
            Err(format!("cannot parse `{}` as a char", words[0]))
        }
    }
}
pub struct Chars();
impl Readable for Chars {
    type Output = Vec<char>;
    fn words_count() -> usize { 1 }
    fn read_words(words: &[&str]) -> Result<Vec<char>, String> {
        Ok(words[0].chars().collect())
    }
}
macro_rules! impl_readable_for_ints {
    ( $( $t:ty )* ) => { $(
        impl Readable for $t {
            type Output = Self;
            fn words_count() -> usize { 1 }
            fn read_words(words: &[&str]) -> Result<$t, String> {
                use std::str::FromStr;
                <$t>::from_str(words[0]).map_err(|_| {
                    format!("cannot parse `{}` as {}", words[0], stringify!($t))
                })
            }
        }
    )* };
}
impl_readable_for_ints!(i8 u8 i16 u16 i32 u32 i64 u64 isize usize f32 f64);
macro_rules! define_one_origin_int_types {
    ( $new_t:ident $int_t:ty ) => {
        #[allow(non_camel_case_types)]
        pub struct $new_t;
        impl Readable for $new_t {
            type Output = $int_t;
            fn words_count() -> usize { 1 }
            fn read_words(words: &[&str]) -> Result<Self::Output, String> {
                <$int_t>::read_words(words).map(|n| n-1)
            }
        }
    };
    ( $new_t:ident $int_t:ty; $( $inner_new_t:ident $inner_int_t:ty );* ) => {
        define_one_origin_int_types!($new_t $int_t);
        define_one_origin_int_types!($($inner_new_t $inner_int_t);*);
    };
}
define_one_origin_int_types!(u8_ u8; u16_ u16; u32_ u32; u64_ u64; usize_ usize);
macro_rules! impl_readable_for_tuples {
    ( $t:ident $var:ident ) => ();
    ( $t:ident $var:ident; $( $inner_t:ident $inner_var:ident );* ) => {
        impl_readable_for_tuples!($($inner_t $inner_var);*);
        impl<$t: Readable, $($inner_t: Readable),*> Readable
            for ($t, $($inner_t),*)
        {
            type Output = ( <$t>::Output, $(<$inner_t>::Output),* );
            fn words_count() -> usize {
                let mut n = <$t>::words_count();
                $(
                    n += <$inner_t>::words_count();
                )*
                n
            }
            #[allow(unused_assignments)]
            fn read_words(words: &[&str]) ->
                Result<Self::Output, String>
            {
                let mut start = 0;
                let $var = <$t>::read_words(
                    &words[start .. start+<$t>::words_count()]
                )?;
                start += <$t>::words_count();
                $(
                    let $inner_var =
                        <$inner_t>::read_words(
                            &words[start .. start+<$inner_t>::words_count()]
                        )?;
                    start += <$inner_t>::words_count();
                )*
                Ok(( $var, $($inner_var),* ))
            }
        }
    };
}
impl_readable_for_tuples!(T8 x8; T7 x7; T6 x6; T5 x5; T4 x4; T3 x3; T2 x2; T1 x1);
pub trait ReadableFromLine {
    type Output;
    fn read_line(line: &str) -> Result<Self::Output, String>;
}
fn split_into_words(line: &str) -> Vec<&str> {
    #[allow(deprecated)]
    line.trim_right_matches('\n').split_whitespace().collect()
}
impl<T: Readable> ReadableFromLine for T {
    type Output = T::Output;
    fn read_line(line: &str) -> Result<T::Output, String> {
        let words = split_into_words(line);
        if words.len() != T::words_count() {
            return Err(format!("line `{}` has {} words, expected {}",
                               line, words.len(), T::words_count()));
        }
        T::read_words(&words)
    }
}
macro_rules! impl_readable_from_line_for_tuples_with_from_iterator {
    ( $u:ident : $( + $bound:path )* => $seq_in:ty, $seq_out:ty; $t:ident $var:ident ) => {
        impl<$u: Readable> ReadableFromLine for $seq_in
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = $seq_out;
            fn read_line(line: &str) -> Result<$seq_out, String> {
                let n = $u::words_count();
                let words = split_into_words(line);
                if words.len() % n != 0 {
                    return Err(format!("line `{}` has {} words, expected multiple of {}",
                                       line, words.len(), n));
                }
                let mut result = Vec::new();
                for chunk in words.chunks(n) {
                    match $u::read_words(chunk) {
                        Ok(v) => result.push(v),
                        Err(msg) => {
                            let flagment_msg = if n == 1 {
                                format!("word {}", result.len())
                            } else {
                                let l = result.len();
                                format!("words {}-{}", n*l + 1, (n+1) * l)
                            };
                            return Err(format!(
                                "{} of line `{}`: {}", flagment_msg, line, msg
                            ));
                        }
                    }
                }
                Ok(result.into_iter().collect())
            }
        }
        impl<T: Readable, $u: Readable> ReadableFromLine for (T, $seq_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = (T::Output, $seq_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let n = T::words_count();
                #[allow(deprecated)]
                let trimmed = line.trim_right_matches('\n');
                let words_and_rest: Vec<&str> = trimmed.splitn(n + 1, ' ').collect();
                if words_and_rest.len() < n {
                    return Err(format!("line `{}` has {} words, expected at least {}",
                                       line, words_and_rest.len(), n));
                }
                let words = &words_and_rest[..n];
                let empty_str = "";
                let rest = words_and_rest.get(n).unwrap_or(&empty_str);
                Ok((T::read_words(words)?, <$seq_in>::read_line(rest)?))
            }
        }
    };
    ( $u:ident : $( + $bound:path )* => $seq_in:ty, $seq_out:ty;
      $t:ident $var:ident, $( $inner_t:ident $inner_var:ident ),+ ) => {
        impl_readable_from_line_for_tuples_with_from_iterator!(
            $u: $(+ $bound)* => $seq_in, $seq_out; $($inner_t $inner_var),+
        );
        impl<$t: Readable, $($inner_t: Readable),+ , $u: Readable> ReadableFromLine
            for ($t, $($inner_t),+ , $seq_in)
        where
            <$u as Readable>::Output: Sized $(+ $bound)*
        {
            type Output = ($t::Output, $($inner_t::Output),+ , $seq_out);
            fn read_line(line: &str) -> Result<Self::Output, String> {
                let mut n = $t::words_count();
                $(
                    n += $inner_t::words_count();
                )+
                #[allow(deprecated)]
                let trimmed = line.trim_right_matches('\n');
                let words_and_rest: Vec<&str> = trimmed.splitn(n + 1, ' ')
                    .collect();
                if words_and_rest.len() < n {
                    return Err(
                        format!("line `{}` has {} words, expected at least {}",
                                line, words_and_rest.len(), n)
                    );
                }
                let words = &words_and_rest[..n];
                let empty_str = "";
                let rest = words_and_rest.get(n).unwrap_or(&empty_str);
                let ($var, $($inner_var),*) =
                    <($t, $($inner_t),+)>::read_words(words)?;
                Ok(($var, $($inner_var),* , <$seq_in>::read_line(rest)?))
            }
        }
    };
}
#[macro_export]
macro_rules! readable_collection {
    ($u:ident => $collection_in:ty, $collection_out:ty) => {
        impl_readable_from_line_for_tuples_with_from_iterator!(
            $u: => $collection_in, $collection_out;
            T8 x8, T7 x7, T6 x6, T5 x5, T4 x4, T3 x3, T2 x2, T1 x1
        );
    };
    ($u:ident : $( $bound:path ),* => $collection_in:ty, $collection_out:ty) => {
        impl_readable_from_line_for_tuples_with_from_iterator!(
            $u: $(+ $bound)* => $collection_in, $collection_out;
            T8 x8, T7 x7, T6 x6, T5 x5, T4 x4, T3 x3, T2 x2, T1 x1
        );
    }
}
readable_collection!(U => Vec<U>, Vec<U::Output>);
readable_collection!(
    U => std::collections::VecDeque<U>, std::collections::VecDeque<U::Output>
);
readable_collection!(
    U: Eq, std::hash::Hash => std::collections::HashSet<U>, std::collections::HashSet<U::Output>
);
readable_collection!(
    U: Ord => std::collections::BTreeSet<U>, std::collections::BTreeSet<U::Output>
);
readable_collection!(
    U: Ord => std::collections::BinaryHeap<U>, std::collections::BinaryHeap<U::Output>
);
pub fn read<T: ReadableFromLine>() -> T::Output {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    T::read_line(&line).unwrap()
}
#[macro_export]
macro_rules! read {
    () => {
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
    };
    ( $pat:pat = $t:ty ) => {
        let $pat = read::<$t>();
    };
    ( $( $pat:pat = $t:ty ),+ ) => {
        read!(($($pat),*) = ($($t),*));
    };
}
#[macro_export]
macro_rules! readls {
    ( $( $pat:pat = $t:ty ),+ ) => {
        $(
            read!($pat = $t);
        )*
    };
}
pub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result = stdin.lock().lines().map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    result
}
#[macro_export]
macro_rules! readx_loop {
    ( |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            for line in stdin.lock().lines() {
                let line = line.expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( |$($pat:pat = $t:ty),*| $body:expr ) => {
        readx_loop!(|($($pat),*) = ($($t),*)| $body);
    };
}
pub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {
    use std::io::{self, BufRead};
    let stdin = io::stdin();
    let result: Vec<T::Output> = stdin.lock().lines().take(n).map(|line_result| {
        let line = line_result.expect("read from stdin failed");
        T::read_line(&line).unwrap()
    }).collect();
    if result.len() < n {
        panic!("expected reading {} lines, but only {} lines are read",
               n, result.len());
    }
    result
}
#[macro_export]
macro_rules! readn_loop {
    ( $n:expr, |$pat:pat = $t:ty| $body:expr ) => {
        {
            use std::io::BufRead;
            let stdin = std::io::stdin();
            let mut lock = stdin.lock();
            for _ in 0..$n {
                let mut line = String::new();
                lock.read_line(&mut line).expect("read from stdin failed");
                let $pat = <$t>::read_line(&line).unwrap();
                $body
            }
        }
    };
    ( $n:expr, |$($pat:pat = $t:ty),*| $body:expr ) => {
        readn_loop!($n, |($($pat),*) = ($($t),*)| $body);
    };
}
pub trait Words {
    fn read<T: Readable>(&self) -> T::Output;
}
impl<'a> Words for [&'a str] {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(self).unwrap()
    }
}
impl<'a> Words for &'a str {
    fn read<T: Readable>(&self) -> T::Output {
        T::read_words(&[self]).unwrap()
    }
}
// END SNIPPETS

use hokudai_hitachi2019_1::Env;
use hokudai_hitachi2019_1::read::{read_v_and_e, read_edges, read_t_max, read_order};

use std::io;
use std::mem;

#[derive(Debug)]
enum Action {
    Waiting,
    Moving {
        start_t: usize,
        path: Vec<usize>, // 始点と終点（ともに店舗）を含む
        prev: usize,
        dist: u16
    }
}
use Action::*;

impl Action {
    fn dest(&self) -> Option<usize> {
        match self {
            &Waiting => None,
            &Moving { ref path, prev, .. } => Some(path[prev+1])
        }
    }
}

struct Agent {
    env: Env,
    orders: Vec<Vec<usize>>,
    t: usize,
    action: Action,
}

impl Agent {
    fn new(env: Env, orders: Vec<Vec<usize>>) -> Agent {
        let shop = env.shop();
        Agent {
            env: env,
            orders: orders,
            t: 0,
            action: Waiting
        }
    }

    fn next_point(&self, path: &[usize], prev: usize, dist: u16) -> (usize, u16) {
        let src = path[prev];
        let dest = path[prev + 1];
        let edge_dist = self.env.dist()[src][dest];
        if dist + 1 == edge_dist {
            (prev + 1, 0)
        } else {
            (prev, dist + 1)
        }
    }

    fn get_path(&self, mut order: Vec<usize>) -> Vec<usize> {
        order.sort();
        order.dedup();
        order.push(self.env.shop());

        let mut res = vec![self.env.shop()];
        for next in order {
            let v = *res.last().unwrap();
            res.extend_from_slice(&self.env.path()[v][next]);
            res.push(next);
        }
        res
    }

    fn order_after(&self, t: usize) -> Vec<usize> {
        self.orders[t+1..self.t+1]
            .iter().cloned().flatten().collect()
    }

    // 目的地を返す
    fn progress(&mut self) -> Option<usize> {
        let (action, dest) = match mem::replace(&mut self.action, Waiting) {
            Waiting => {
                let mut order = self.orders[self.t as usize].clone();
                if order.is_empty() {
                    (Waiting, None)
                } else {
                    let path = self.get_path(order);
                    let (prev, dist) = self.next_point(&path, 0, 0);
                    let dest = path[1];
                    let action = Moving {
                        start_t: self.t,
                        path: path,
                        prev: prev,
                        dist: dist
                    };
                    (action, Some(dest))
                }
            },
            Moving { start_t, path, prev, dist } => {
                let dest = path[prev + 1];
                let (v, d) = self.next_point(&path, prev, dist);
                let action = if v < path.len() - 1 {
                    Moving {
                        start_t: start_t,
                        path: path,
                        prev: v,
                        dist: d
                    }
                } else {
                    let order = self.order_after(start_t);
                    if order.is_empty() {
                        Waiting
                    } else {
                        let path = self.get_path(order);
                        Moving {
                            start_t: self.t,
                            path: path,
                            prev: 0,
                            dist: 0
                        }
                    }
                };
                (action, Some(dest))
            }
        };
        self.action = action;
        self.t += 1;
        dbg!(self.t);
        dbg!(&self.action);
        dest
    }
}

fn main() {
    let stdin = io::stdin();
    let mut handle = stdin.lock();
    // test of dijkstra
    let (v, e) = read_v_and_e(&mut handle);
    let edges = read_edges(&mut handle, v, e);
    let t_max = read_t_max(&mut handle);
    let t_last = t_max / 100 * 95;
    let mut orders = Vec::new();
    for _ in 0..t_max {
        orders.push(read_order(&mut handle));
    }

    let mut agent = Agent::new(Env::new(v, edges, t_max), orders);
    for _ in 0..t_max {
        match agent.progress() {
            None => println!("-1"),
            Some(v) => println!("{}", v+1)
        }
    }
}


Measured memory_bytes: 45308