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:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
#PROBL = 1
MAXVISIT = 400
SPLITTHR = 44
HISTTHR = -1
SPLITTHR4 = 80
HISTTHR4 = 8

def ddprint(x):
  if DBG:
    print(x)
    sys.stdout.flush()

def trigger():
    return (len(loadhash) > 0)

def nxtnode():
    global lastnd, workreq, nxtndary
    tgt = workreq[0] if len(workreq)>0 else 1
    #ddprint("in nxtnode lastnd {} wr0 {} tgt {} ret {}".format(\
    # lastnd, workreq[0] if len(workreq)>0 else -1, tgt, nxtndary[lastnd][tgt]))
    return nxtndary[lastnd][tgt]

def atdepot():
    return (lastnd==1 and distfromlast==0)

def stay():
    #print(-1, flush=True)
    print(-1)
    sys.stdout.flush()

def readput():
    n = inn()
    for i in range(n):
        inn()

def readverd():
    v = input().strip()
    if v != 'OK':
        exit()
    readput()

def move():
    global distfromlast, lastnd, workreq, pendreq, loadhash
    nxtnd = nxtnode()
    #print(nxtnd, flush=True)
    print(nxtnd)
    sys.stdout.flush()
    distfromlast += 1
    if distfromlast == dist[lastnd][nxtnd]: # reach nxtnd
        distfromlast = 0
        if nxtnd in workreq:
            workreq.remove(nxtnd)
        if nxtnd in loadhash:
                del loadhash[nxtnd]
        if nxtnd==1:
                for z in pendreq:
                    if z[1] not in loadhash:
                        loadhash[z[1]] = []
                    loadhash[z[1]].append(z[2])
                pendreq = []
        lastnd = nxtnd

def ufinit(n):
    global ufary, ufrank
    ufary = [i for i in range(n)]
    ufrank = [0] * n

def ufroot(i):
    p = ufary[i]
    if p==i:
        return p
    q = ufroot(p)
    ufary[i] = q
    return q

def ufmerge(i,j):
    global ufary, ufrank
    ri = ufroot(i)
    rj = ufroot(j)
    if ri==rj:
        return
    if ufrank[ri]>ufrank[rj]:
        ufary[rj] = ri
    else:
        ufary[ri] = rj
        if ufrank[ri]==ufrank[rj]:
            ufrank[rj] += 1

def setwork():
    global workreq, lastside, loadhash
    visset = set(loadhash.keys()) | set(workreq)
    vislist = list(visset)
    vv = len(vislist)
    if vv==1:
        workreq = vislist
        return
    if vv>SPLITTHR4 and sum(hist)>HISTTHR4:
        pt = [0,0,0,0]
        for x in vislist:
            suf = (0 if x in gr4[0] else \
              1 if x in gr4[1] else 2 if x in gr4[2] else 3)
            pt[suf] += sum([t-y for y in loadhash[x]])
        mx = max(pt)
        lastside = (0 if mx==pt[0] else \
            1 if mx==pt[1] else 2 if mx==pt[2] else 3)
        vislist = [x for x in vislist if x in gr4[lastside]]
        vv = len(vislist)
    elif vv>SPLITTHR and sum(hist)>HISTTHR:
        pt = [0,0]
        for x in vislist:
            suf = (0 if x in gr[0] else 1)
            pt[suf] += sum([t-y for y in loadhash[x]])
        lastside = (0 if pt[0]>=pt[1] else 1)
        vislist = [x for x in vislist if x in gr[lastside]]
        vv = len(vislist)
        lastside = 1 - lastside

    # Clark & Wright
    e = {}
    f = {}
    for x in vislist:
        e[x] = []
    ufinit(V+1)
    #ddprint("e pre")
    #ddprint(e)
    for _ in range(vv-1):
        mx = -1
        for i in e:
            for j in e:
                if ufroot(i)==ufroot(j):
                    continue
                df = dist[i][1] + dist[1][j] - dist[i][j]
                if df>mx:
                    mx = df
                    mxi = i
                    mxj = j
        i = mxi
        j = mxj
        #ddprint("connect {},{}".format(i,j))
        e[i].append(j)
        e[j].append(i)
        ufmerge(i,j)
        if len(e[i])==2:
            f[i] = e[i]
            del e[i]
        if len(e[j])==2:
            f[j] = e[j]
            del e[j]
    # now len(e) is 2.  find the first
    #ddprint("e {}".format(e))
    #ddprint("f {}".format(f))
    ek = list(e.keys())
    p = ek[0]
    #q = ek[1]
    prev = p
    cur = e[p][0]
    workreq = [p,cur]
    for i in range(vv-2):
        p = cur
        cur = f[p][0]
        if cur==prev:
            cur = f[p][1]
        prev = p
        workreq.append(cur)

    acct = t
    prev = 1
    fwdpt = 0
    for i in range(len(workreq)):
        x = workreq[i]
        for y in loadhash[x]:
            fwdpt += acct - y
        acct += dist[prev][x]
        prev = x

    acct = t
    prev = 1
    revpt = 0
    for i in range(len(workreq)):
        x = workreq[len(workreq)-1-i]
        for y in loadhash[x]:
            revpt += acct - y
        acct += dist[prev][x]
        prev = x

    if revpt<fwdpt:
        workreq.reverse()
    #ddprint("w {}".format(workreq))

def findcorners():
    mx = -1
    for i in range(1,V+1):
        for j in range(1,V+1):
            d = dist[i][j]
            if d>mx:
                mx = d
                mxi = i
                mxj = j
    c1 = mxi
    c3 = mxj
    mx = -1
    for i in range(1,V+1):
        d = dist[i][c1]+dist[i][c3]
        if d>mx:
            mx = d
            mxi = i
    c2 = mxi
    mx = -1
    for i in range(1,V+1):
        d = dist[i][c1]+dist[i][c3]+dist[i][c2]
        if d>mx:
            mx = d
            mxi = i
    c4 = mxi
    d1 = dist[1][c1]
    d2 = dist[1][c2]
    d3 = dist[1][c3]
    d4 = dist[1][c4]
    if min(d1,d3)<min(d2,d4):
        z = (c2,c4)
    else:
        z = (c1,c3)

    a = []
    for i in range(2,V+1):
        df = dist[i][z[0]]-dist[i][z[1]]
        a.append((df,i))
    a.sort()
    g0 = [x[1] for x in a[:(V-1)//2]]
    g1 = [x[1] for x in a[(V-1)//2:]]
    #g1 = [] #g0 = []   got worse
    #for i in range(2,V+1):
    #    df = dist[i][z[0]]-dist[i][z[1]]
    #    if df<0:
    #        g0.append(i)
    #    else:
    #        g1.append(i)

    tricent = 0
    if 3*d1 < min([d2,d3,d4]):
        tricent = c1
    elif 3*d2 < min([d1,d3,d4]):
        tricent = c2
    elif 3*d3 < min([d1,d2,d4]):
        tricent = c3
    elif 3*d4 < min([d1,d2,d3]):
        tricent = c4

    h0 = []
    h1 = []
    h2 = []
    h3 = []
    if tricent==0:
      for i in range(2,V+1):
        d1 = dist[i][c1]
        d2 = dist[i][c2]
        d3 = dist[i][c3]
        d4 = dist[i][c4]
        mn = min([d1,d2,d3,d4])
        if mn==d1:
            h0.append(i)
        elif mn==d2:
            h1.append(i)
        elif mn==d3:
            h2.append(i)
        elif mn==d4:
            h3.append(i)
    else:
        if tricent==c1:
            ccc = [c2,c3,c4]
        elif tricent==c2:
            ccc = [c1,c3,c4]
        elif tricent==c3:
            ccc = [c1,c2,c4]
        else:  #if tricent==c4:
            ccc = [c1,c2,c3]
        for i in range(2,V+1):
            d1 = dist[i][ccc[0]]
            d2 = dist[i][ccc[1]]
            d3 = dist[i][ccc[2]]
            mn = min([d1,d2,d3])
            if mn==d1:
                h0.append(i)
            elif mn==d2:
                h1.append(i)
            else:  #if mn==d3:
                h2.append(i)
            # h3 remains empty

    return (g0,g1,h0,h1,h2,h3)

# # # # main start # # # #
ddprint("start")
#prob = PROBL # int(sys.argv[1])

V, E = inm()
es = [[] for i in range(V+1)]
dist = [[9999]*(V+1) for i in range(V+1)]

for i in range(V+1):
    dist[i][i] = 0

for i in range(E):
    a, b, c = inm()
    #a, b = a-1, b-1
    es[a].append((b,c))
    es[b].append((a,c))
    dist[a][b] = dist[b][a] = c

if DBG:
    for i,z in enumerate(es):
        print(str(i)+' ' + str(z))

# Warshal-Floyd
for k in range(1,V+1):
    for i in range(1,V+1):
        for j in range(1,V+1):
            dist[i][j] = min(dist[i][j], \
                           dist[i][k]+dist[k][j])
ddprint("WS done")

nxtndary = [[0]*(V+1) for i in range(V+1)]
for i in range(1,V+1):
    for j in range(1,V+1):
        if j==i:
            continue
        found = False
        for z in es[i]:
            k = z[0]
            if dist[i][j] == z[1]+dist[k][j]:
                nxtndary[i][j] = k
                found = True
                break
        if not found:
            print("nxtndary ERR")
            exit()

g0,g1,h0,h1,h2,h3 = findcorners()
gr = [g0,g1]
gr4 = [h0,h1,h2,h3]
lastside = 0

F = inl()
if len(F)==1:
    prob = 1
    tt = F[0]
else:
    prob = 2
    tt = inn()
pendreq = []
workreq = []
loadhash = {}
lastnd = 1
distfromlast = 0
hist = []
for t in range(tt):
    if DBG and t>3400:
        exit()

    # read a new req if any
    n = inn()
    hist.append(n)
    if len(hist)>20:
        hist = hist[1:]
    if n==1:
        new_id, dst = inm()
        #ddprint("new req id {} dst {}".format(new_id, dst))
        if not atdepot():
            pendreq.append((new_id, dst, t))
        else:
            if dst not in loadhash:
                loadhash[dst] = []
            loadhash[dst].append(t)
    if prob==2:
        readput()
    # determine action
    if atdepot():
        if trigger():
            setwork()
            if len(workreq)>0:
                move()
            else:
                stay()
        else:
            stay()
    else:
        move()
    if prob==2:
        readverd()