import math
out = open('out6.txt','a')
class graph:
    INF = 10000
    G = []
    Path = []
    E = 0
    V = 0
    def __init__(self):
        dataRaw = raw_input()
        raw = dataRaw.strip().split(' ')
        self.E = int(raw[0])+1
        self.V = int(raw[1])
        self.G = [[self.INF] * (self.E) for i in range(self.E)]
        self.Path = [[0] * (self.E) for i in range(self.E)]
        for _ in range(0,self.V):
            dataRaw = raw_input()
            raw = dataRaw.strip().split(' ')
            i = int(raw[0])
            j = int(raw[1])
            k = int(raw[2])
            self.G[i][j] = k
            self.G[j][i] = k

        for i in range(1,self.E):
            self.G[i][i] = 0

        for k in range(0,self.E):
            for i in range(0, self.E):
                for j in range(0, self.E):
                    if self.G[i][k]+self.G[k][j] < self.G[i][j]:
                        self.G[i][j] = self.G[i][k]+self.G[k][j]
                        self.Path[i][j] = k
    def shortPath(self,i,j):
        path = []

        def core(i,j,path):
            if self.Path[i][j] == 0:
                if len(path) == 0 or path[-1] != i:
                    path.append(i)
                path.append(j)
                return
            else :
                core(i, self.Path[i][j],path)
                core(self.Path[i][j], j, path)
        core(i, j,path)
        path.pop(0)
        return path

class driver :
    plan = []
    untakeorder = set()
    order = dict()
    takeButNotdeliver = set()
    location = 1
    nextSegmentLeftTime = 0
    target = 1

    def __init__(self,g):
        self.map = g

    def routeLazyWithHome(self,currentTime):
        if len(self.plan) > 1:
            self.target = self.plan[0]
            self.nextSegmentLeftTime = self.map.G[self.location][self.target]
            self.plan.pop(0)
            return

        # choose every time choose nearest
        if len(self.order)==0 and len(self.plan) == 0:
            self.order[1] = currentTime



        last = self.location
        if len(self.plan) > 0:
            last = self.plan[-1]

        if len(self.untakeorder) * len(self.order) > 0 and len(self.untakeorder) / len(self.order) > 30:
            path = self.map.shortPath(last, 1)
            for j in path:
                self.plan.append(j)
            if len(self.plan) > 0:
                self.target = self.plan[0]
                self.nextSegmentLeftTime = self.map.G[self.location][self.target]
                self.takeButNotdeliver.discard(self.plan[0])
                self.plan.pop(0)
            return

        # out.write("| last : " + str(last) +" "+ str(type(last)) )
        if len(self.order) > 0:
            id = 1
            dis = 1e5
            for i in self.order.keys():
                if self.map.G[i][last] < dis:
                    dis = self.map.G[i][last]
                    if currentTime-self.order[i] > 1500:
                        dis -= int(math.log(currentTime-self.order[i]+1,10))
                    id = i
            path = self.map.shortPath(last,id)
            for j in path:
                self.plan.append(j)
            self.takeButNotdeliver.add(id)
            del self.order[id]


            dis2 = 1e5
            for i in self.untakeorder:
                if self.map.G[i][1] < dis2:
                    dis2 = self.map.G[i][1]
            if dis2+self.map.G[last][1] < dis :
                self.order[1] = currentTime

            if len(self.untakeorder) * len(self.order) > 0 and len(self.untakeorder) / len(self.order) > 5:
                self.order[1] = currentTime

        if len(self.plan) > 0:
            self.target = self.plan[0]
            self.nextSegmentLeftTime = self.map.G[self.location][self.target]
            self.takeButNotdeliver.discard(self.plan[0])
            self.plan.pop(0)

    def routeoOnshop(self,currentTime):

        # choose every time choose nearest
        if len(self.order)==0 and len(self.plan) == 0:
            self.order[1] = currentTime


        last = self.location
        if len(self.plan) > 0:
            last = self.plan[-1]

        # out.write("| last : " + str(last) +" "+ str(type(last)) )
        # print "order : ",self.order

        if len(self.order) > 0:
            directDis = 0
            for i in self.order.keys():
                directDis += self.map.G[1][i]
            ignoreSet = set()

            ok = False
            while len(self.order) > 5 and len(ignoreSet) < 5:
                id = 1
                dis = 1e5
                for i in self.order.keys():
                    if i not in ignoreSet:
                        if self.map.G[i][last] < dis:
                            dis = self.map.G[i][last]
                            id = i
                currDis = 0
                for i in self.order.keys():
                    currDis += self.map.G[id][i]
                if currDis <= directDis :
                    winner = id
                    # print "winner : ",winner
                    path = self.map.shortPath(last, winner)
                    # print "path : ", path
                    ok = True
                    for j in path:
                        self.plan.append(j)
                    del self.order[winner]
                    self.takeButNotdeliver.add(winner)
                    break
                else :
                    ignoreSet.add(id)


            if ok == False :
                id = 1
                dis = 1e5
                for i in self.order.keys():
                    if self.map.G[i][last] < dis:
                        dis = self.map.G[i][last]
                        id = i
                path = self.map.shortPath(last, id)
                for j in path:
                    self.plan.append(j)
                del self.order[id]
                self.takeButNotdeliver.add(id)




        if len(self.plan) > 0:
            self.target = self.plan[0]
            self.nextSegmentLeftTime = self.map.G[self.location][self.target]
            self.plan.pop(0)

    def move(self,method):
        #out.write('-1\n')
        #return

        if self.location == self.target:
            out.write('-1\n')
            print (-1)
            return

        assert(self.nextSegmentLeftTime > 0)
        self.nextSegmentLeftTime = self.nextSegmentLeftTime - 1
        print (self.target)
        out.write(str(self.target) + '\n')
        if self.nextSegmentLeftTime == 0:
            self.location = self.target

    def onRoute(self):
        return self.nextSegmentLeftTime != 0



class timer :
    orders = []
    times = []
    orderIndex = 0
    currTime = 0
    Tmax = 0
    def __init__(self):
        Tmax = raw_input()
        self.Tmax = int(Tmax)
        for i in range(0, self.Tmax):
            n = raw_input()
            n = int(n)

            if n==0 :
                continue
            else :
                dataRaw = raw_input()
                data = dataRaw.strip().split(' ')
                self.times.append(i+1)
                self.orders.append(int(data[1]))
        #print self.times

    def run(self,driver):
        while self.currTime < self.Tmax:
            self.currTime = self.currTime + 1
            '''
            out.write ("================================\n")
            out.write ("curr time : " + str(self.currTime))

            out.write ("status before : ")
            out.write ("shop status : " + str(shop.order))
            out.write ("driver status : ")
            out.write ("order : " + str(driver.order),)
            out.write ("| plan : " + str(driver.plan),)
            out.write ("| on route : " + str(driver.onRoute()))
            out.write ("| location : " + str(driver.location),)
            out.write ("| target : " + str(driver.target),)
            out.write ("| left time : " + str(driver.nextSegmentLeftTime) + '\n')
            '''
            # add goods
            if self.orderIndex < len(self.times) and self.currTime == self.times[self.orderIndex]:
                if driver.map.G[1][self.orders[self.orderIndex]] < 10000:
                    driver.untakeorder.add(self.orders[self.orderIndex])
                self.orderIndex = self.orderIndex + 1

            if driver.onRoute() == False and driver.location == 1:
                for each in driver.untakeorder:
                    if each not in driver.order.keys():
                        driver.order[each] = self.currTime
                driver.untakeorder = set()

            if driver.onRoute() == False:
                if driver.location == 1 :
                #    print "curr time stamp :",str(self.currTime)
                    driver.routeoOnshop(self.currTime)
                else:
                    driver.routeLazyWithHome(self.currTime)

            driver.move("CheckEveryTime")

            # debug
            '''
            out.write ("status after : ")
            out.write ("shop status : " + str(shop.order))
            out.write ("driver status : ")
            out.write ("order : " + str(driver.order),)
            out.write ("| plan : " + str(driver.plan),)
            out.write ("| on route : " + str(driver.onRoute()))
            out.write ("| location : " + str(driver.location),)
            out.write ("| target : " + str(driver.target),)
            out.write ("| left time : " + str(driver.nextSegmentLeftTime) + '\n')
            out.write ("================================\n")
            '''

if __name__=="__main__":

    g = graph()


    driver = driver(g)
    ti = timer()
    ti.run(driver)


Measured memory_bytes: 7556