Problem: Requirements

* All inputs are of non-negative integer value.
* T_{\text{max}} = 10000
* 200 \leq |V| \leq 400
* 1.5 |V| \leq |E| \leq 2 |V|
* 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
* 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
* The given graph has no self-loops / multiple edges and is guaranteed to be connected.
* 0 \leq N_{\text{new}} \leq 1
* 1 \leq \mathrm{new\\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}}). Note: If all orders are generated by the order generation rule as explained above, the total number of orders is at most T_{\text{last}}+1. Therefore, the possible range of \mathrm{new\\_id}_{i} should be from 1 to T_{\text{last}}+1.
* 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
* The order IDs \mathrm{new\\_{id}}_i are unique.

Input Format

Input is provided in the following form:


|V| |E|
u_{1} v_{1} d_{u_{1}, v_{1}}
u_{2} v_{2} d_{u_{2}, v_{2}}
:
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
T_{\text{max}}
\mathrm{info}_{0}
\mathrm{info}_{1}
:
\mathrm{info}_{T_{\text{max}}-1}


* In the first line |V| denotes the number of vertices, while |E| denotes the number of edges.
* The following |E| lines denote the edges of the graph. In particular, in the ith line u_{i} and v_{i} denote the edge connecting u_{i} and v_{i} and d_{u_{i}, v_{i}} the corresponding distance.
* The following line denotes the number of steps T_{\text{max}}.



In the following line, \mathrm{info}_t is information about the order from the customer that occurs at time t. \mathrm{info}_t is given in the form:


N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}


* N_{\text{new}} represents the number of new orders which appear at time t.
* The next N_{\text{new}} lines give the newly generated order information. The i-th order information indicates that the order ID \mathrm{new\\_{id}}_i of the new order, while \mathrm{dst}_i denotes the vertex to which the customer wishes the order to be delivered.
* Note: If N_{\text{new}}=0, there are no new lines.

Output Format

The Output expects T_{\text{max}} integers in the format specified below.


\mathrm{command}_{0}
\mathrm{command}_{1}
:
\mathrm{command}_{T_{\text{max}}-1}


In particular, \mathrm{command}_{i} shall specify the movement of the delivery car by using one of the following two options:

1) `stay`, if the car shall not move:


-1


2) `move w`, if the car shall be moved one step towards the neighboring vertex w


w


Note that in case of 2) w has to satisfy the following conditions:

* w \in V
* If the car is at vertex u: \left\\{ u, w \right\\} \in E .
* If the car is on the edge \left\\{ u, v \right\\}, w must either satisfy u = w or v = w.



* * *

Examples

Input




Output




Input

5 7
1 2 5
5 3 4
2 4 8
1 5 1
2 3 3
4 5 3
4 3 9
4
1
1 2
1
2 5
1
3 4
0


Output

2
-1
1
5

Solution (in PYTHON3):

Solution:
from collections import defaultdict
import random

from logging import getLogger, StreamHandler, DEBUG, ERROR
from functools import lru_cache

logger = getLogger(__name__)
handler = StreamHandler()
handler.setLevel(DEBUG)
logger.setLevel(ERROR)
logger.addHandler(handler)
logger.propagate = False

logger.debug("HEADER")

class Maps(object):
    def __init__(self):
        self.readinputs()

    # recieve |V| and |E|
    def readinputs(self):
        self.V, self.E = map(int, input().split())
        self.es = [[] for i in range(self.V)]
        self.Mes = [[0]*self.V for i in range(self.V)]
        self.graph = Graph()
        self.car = Car()
        self.here = ('v', 0)
        self.plan = []

        for _ in range(self.E):
            # recieve edges
            a, b, c = map(int, input().split())
            a, b = a-1, b-1
            self.es[a].append((b,c))
            self.es[b].append((a,c))
            self.Mes[a][b] = c
            self.Mes[b][a] = c
            self.graph.add_edge(a,b,c)

        self.T = int(input())

        # recieve info
        self.info = [[] for i in range(self.T)]
        for t in range(self.T):
            Nnew = int(input())
            for _ in range(Nnew):
                new_id, dst = map(int, input().split())
                dst = dst-1
                self.info[t].append((new_id, dst))

        logger.debug("Set status")
        logger.debug("Info :")
        logger.debug(self.info)

    def get_plan(self):
        return self.plan

    def has_plan(self):
        if self.plan == []:
            return False
        else:
            return True

    def get_here(self):
        return self.here
    
    def set_here(self, here):
        self.here = here
    
    def next_place(self, here, command):
        if command == -2:
            return here
        else:
            to = command
            if here[0] == 'v':
                dist = self.Mes[here[1]][to]
                if dist == 0:
                    raise ValueError('Dist has not 0')                
                elif dist == 1:
                    return ('v', to)
                else:
                    return ('e', here[1], to, 1) # You can move 1m per time
            elif here[0] == 'e':
                if here[2] == to:
                    if here[3] + 1 < self.Mes[here[1]][here[2]]:
                        return ('e', here[1], here[2], here[3] + 1)
                    elif here[3] + 1 == self.Mes[here[1]][here[2]]:
                        return ('v', here[2])
                    else:
                        raise ValueError('Distance error!')

                elif here[1] == to:
                    if here[3] - 1 > 0:
                        return ('e', here[1], here[2], here[3] - 1)
                    elif here[3] - 1 == 0:
                        return ('v', here[1])
                    else:
                        raise ValueError('Distance error!')
            else:
                raise ValueError('Here has vertex or edge status')

    def get_command(self, here, plan):
        if here[0] == 'v':
            # you are in vertex
            if plan == []:
                # stay at 0
                return -2
            elif here[1] == plan[-1]:
                # arrive goal
                return -2
            else:
                return plan[plan.index(here[1]) + 1]
        elif here[0] == 'e':
            # you are in edge
            return here[2]
        else:
            raise ValueError('Here has vertex or edge status')

    def move(self):
        where = [('v', 0)] # ('v', here) or ('e', from, to, dist)
        dist_time = 0
        self.path = [0]*self.T
        last_stay_0 = 0
        for t in range(self.T):
            now_where = where[-1]

            logger.debug("----------Time----------")
            logger.debug(t)
            logger.debug("Here is  :")
            logger.debug(now_where)
            logger.debug("parcel  :")
            logger.debug(self.info[t])

            if now_where[0] == 'v':
                # 荷物を拾ったりおろしたり
                if now_where[1] == 0:
                    logger.debug("Car Parameter :")
                    logger.debug("Last stay at 0 :")
                    logger.debug(last_stay_0)
                    logger.debug("Picking up parcel is :")
                    for parcel in self.info[last_stay_0: t + 1]:
                        logger.debug(parcel)
                        self.car.pickup(parcel)
                    last_stay_0 = t + 1
                else:
                    self.car.unload(now_where[1])
            
            logger.debug("Car Box  :")
            logger.debug(self.car.box)
            if self.car.box == []:
                logger.debug("Car Box is vacant")
                if now_where[0] == 'v' and now_where[1] == 0:
                    self.path[t] = -2
                    where.append(('v', 0))
                    logger.debug("Time " + str(t) + " command is :")
                    logger.debug(self.path[t])
                    logger.debug("No parcel and stay at 1. Continue")
                    continue

            if not self.has_plan():
                logger.debug("--Set plan--")
                logger.debug("-Now-")
                logger.debug(now_where)
                logger.debug("-Dests-")
                logger.debug(self.car.show_dest())
                if now_where[1] != 0:
                    goal = 0
                    dist_time += 1
                else:
                    goal = self.select_goal(now_where[1], self.car.show_dest())
                    dist_time += 1
                logger.debug("Set Goal is :")
                logger.debug(goal)
                self.plan = wrap_dijsktra(self.graph, now_where[1], goal)
            logger.debug("Time " + str(t) + " plan is :")
            logger.debug(self.plan)

            if self.plan == []:
                logger.debug("Time " + str(t) + " has no plan")
                self.path[t] = -2
                continue

            command = self.get_command(now_where, self.plan)
            self.path[t] = command
            logger.debug("Time " + str(t) + " command is :")
            logger.debug(command)
            where.append(self.next_place(now_where, command))
            logger.debug("Time " + str(t) + " next place is :")
            logger.debug(where[-1])
            
            if where[-1][0] == 'v' and where[-1][1] == self.plan[-1]:
                logger.debug("Time " + str(t) + " we arrive at goal !")
                self.plan = []

    def select_goal(self, here, dests):
        # logger.debug('--select goal--')
        # logger.debug('Here is : ')
        # logger.debug(here)
        dist = dict()
        for dest in dests:
            # logger.debug("Dest is : ")
            # logger.debug(dest)
            path = wrap_dijsktra(self.graph, here, dest)
            # logger.debug("path is : ")
            # logger.debug(path)
            dist[dest] = self.dist_path(path)
        nearby = min(dist, key=dist.get)
        return nearby

    def dist_path(self, path):
        distance = 0
        for n in range(len(path)-1):
            distance += self.Mes[path[n]][path[n+1]]
        return distance

    def output(self):
        for t in range(self.T) :
            print(self.path[t] + 1)


class Graph():
    def __init__(self):
        """
        self.edges is a dict of all possible next nodes
        e.g. {'X': ['A', 'B', 'C', 'E'], ...}
        self.weights has all the weights between two nodes,
        with the two nodes as a tuple as the key
        e.g. {('X', 'A'): 7, ('X', 'B'): 2, ...}
        """
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        # Note: assumes edges are bi-directional
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight

class Car(object):
    def __init__(self):
        self.box = []
        # self.dest = set()
    
    def pickup(self, parcel):
        # parcel [] or [(new_id, dst)]
        if parcel == []:
            pass
        else:
            self.box.append(parcel[0])
            # self.dest.add(parcel[0])
    
    def unload(self, vertex):
        self.box = [x for x in self.box if x[1] != vertex]
        # self.dest = {x for x in self.box if x[1] != vertex}
 
    def show_dest(self):
        dest = set()
        for x in self.box:
            # show dst only.
            dest.add(x[1])
        if len(dest) == 0:
            dest.add(0)
        return list(dest)


def wrap_dijsktra(graph, initial, end):
    if initial == end:
        return []
    elif initial < end:
        return dijsktra(graph, initial, end)
    else:
        return dijsktra(graph, end, initial)[::-1]

@lru_cache(maxsize=80000)
def dijsktra(graph, initial, end):
    # shortest paths is a dict of nodes
    # whose value is a tuple of (previous node, weight)
    shortest_paths = {initial: (None, 0)}
    current_node = initial
    visited = set()
    
    while current_node != end:
        visited.add(current_node)
        destinations = graph.edges[current_node]
        weight_to_current_node = shortest_paths[current_node][1]

        for next_node in destinations:
            weight = graph.weights[(current_node, next_node)] + weight_to_current_node
            if next_node not in shortest_paths:
                shortest_paths[next_node] = (current_node, weight)
            else:
                current_shortest_weight = shortest_paths[next_node][1]
                if current_shortest_weight > weight:
                    shortest_paths[next_node] = (current_node, weight)
        
        next_destinations = {node: shortest_paths[node] for node in shortest_paths if node not in visited}
        if not next_destinations:
            return "Route Not Possible"
        # next node is the destination with the lowest weight
        current_node = min(next_destinations, key=lambda k: next_destinations[k][1])
    
    # Work back through destinations in shortest path
    path = []
    while current_node is not None:
        path.append(current_node)
        next_node = shortest_paths[current_node][0]
        current_node = next_node
    # Reverse path
    path = path[::-1]
    return path

if __name__ == "__main__":
    # @profile('time', 5)
    def main():
        M = Maps()
        M.move()
        M.output()

    main()