#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<double,int> pdi;

const int64_t CYCLES_PER_SEC=2800000000;
struct Timer {
	int64_t start;
	Timer() { reset(); }
	void reset() { start = getCycle(); }
	inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
	inline int64_t getCycle() {
		uint32_t low, high;
		__asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
		return ((int64_t)low) | ((int64_t)high << 32);
	}
};
Timer timer;
double LN[65536];
const int INF=1000100010;
struct Rand {
	uint32_t x,y,z,w;
	static constexpr double iDouble=1.0/(1LL<<32);
	Rand() {
		x=123456789;y=362436069;z=521288629;w=88675123;
	}
	void setseed(uint32_t seed){z^=seed;}
	uint32_t nextInt(uint32_t n) {
		uint32_t t=x^(x<<11);
		x=y;y=z;z=w;
		w=(w^(w>>19))^(t^(t>>8));
		return w%n;
	}
	uint32_t nextInt() {
		uint32_t t=x^(x<<11);
		x=y;y=z;z=w;
		return w=(w^(w>>19))^(t^(t>>8));
	}
	double nextDouble() {return nextInt()*iDouble;}
} rnd;

int V,E,Tmax;
int Nnew,Nput,Nacv;
vector<pint> G[401];
int F[401];
int dist[401][401],edgecost[401][401];
int parent[401];
vector<int> route[401][401];
set<int> order,carry;
int id_v[10001],ordtime[10001],turn=0;
int SRC,DST;
double p_t=0.0;
int ordcnt[401],carcnt[401];

vector<int> perm1,bperm1;
int mnid[401],mndist[401];
vector<pint> sortp;
vector<int> tmpvec;
bool ptflag=false,outf=false;
int VC=10,curcent=0;
set<int> cent[4];
vector<int> remv;
int countv[4];
int improveRoute(){
    int num=0,retv=-1,vn=90;//V/20+60;
    int costtime=0;
    if(V==400)vn=120;
    if(turn>=9500) vn=INF;
    memset(mnid,0x3f,sizeof(mnid));
    map<int,int> mp;
    sortp.clear();

    memset(mndist,0,sizeof(mndist));
    if(carry.size()>10){
        for(auto it:carry){
            tmpvec.clear();
            for(auto it2:carry){
                if(it!=it2){
                    tmpvec.pb(dist[id_v[it]][id_v[it2]]);
                }
            }
            sort(tmpvec.begin(),tmpvec.end());
            int tmp=0;
            rep(i,5) tmp+=tmpvec[i];
            mndist[id_v[it]]=tmp*tmp;
        }
    }

    for(auto it:carry){
        ++mp[id_v[it]];
        mnid[id_v[it]]=min(mnid[id_v[it]],it);
    }
    remv.clear();
    if(mp.size()>20&&turn<9500){
        for(auto it:mp){
            if(cent[curcent].count(it.first)>0){
                sortp.pb(1,it.first);
            }
            else remv.pb(it.first);
        }
        ++curcent;
        curcent%=4;
    }
    else{
        for(auto it:mp){
            sortp.pb(1,it.first);
        }
    }
    perm1.clear();
    perm1.pb(SRC);
    //sort(sortp.begin(),sortp.end());
    for(auto it:sortp){
        perm1.pb(it.second),++num;
    }
    perm1.pb(0);
    VC=perm1.size();
    retv=perm1[1];
    if(perm1.size()>2){
        FOR(i,1,perm1.size()){
            costtime+=dist[perm1[i-1]][perm1[i]];
        }
    }
    bperm1=perm1;
    if(bperm1.size()<=3) return bperm1[1];
    double curscore=costtime,bestscore=curscore;
    num=max((1<<min(num,20)),128);
    if(turn>=9500) num=(1<<26);
    double ts,starttemp=1.5,endtemp=0.001,invtl=1.0/num;
    int nxcost,precost;
    rep(loop,num){
        ts=starttemp+(endtemp-starttemp)*loop*invtl;
        int sz1=perm1.size();
        int id1=rnd.nextInt(sz1-2),id2=rnd.nextInt(sz1-2);
        if(id1==id2) id2=(id2+1)%(sz1-2);
        ++id1,++id2;
        if(id1>id2) swap(id1,id2);

        precost=dist[perm1[id1-1]][perm1[id1]]
                    +dist[perm1[id2]][perm1[id2+1]];
        nxcost=dist[perm1[id1-1]][perm1[id2]]
                    +dist[perm1[id1]][perm1[id2+1]];

        double diff=precost-nxcost;
		if(diff>=0||diff>LN[rnd.nextInt()&65535]*ts){
            curscore-=diff;
            reverse(perm1.begin()+(id1),perm1.begin()+(id2+1));
            if(bestscore>curscore){
                bestscore=curscore;
                bperm1=perm1;
            }
        }
        
        
        
    }
    
    ll sum1=0,sum2=0;
    int tsz=bperm1.size();
    if(turn>=9500){
        int ct1=turn,ct2=turn,cnt1=0,cnt2=0;
        FOR(i,1,tsz){
            ct1+=dist[bperm1[i-1]][bperm1[i]];
            ct2+=dist[bperm1[tsz-i]][bperm1[tsz-i-1]];
            if(ct1<Tmax) cnt1+=carcnt[bperm1[i]];
            if(ct2<Tmax) cnt2+=bperm1[tsz-i-1];
        }
        if(cnt1<cnt2){
            reverse(bperm1.begin(),bperm1.end());
        }
    }
    else{
        for(auto it:remv){
            FOR(i,1,bperm1.size()){
                if(dist[bperm1[i-1]][bperm1[i]]
                >=dist[bperm1[i-1]][it]+dist[it][bperm1[i]]){
                    bperm1.insert(bperm1.begin()+i,it);
                    break;
                }
            }
        }
    }
    return bperm1[1];
}
void improveRoute2(){
    memset(mnid,0x3f,sizeof(mnid));
    map<int,int> mp;
    sortp.clear();
    int num=0;
    for(auto it:carry){
        ++mp[id_v[it]];
        mnid[id_v[it]]=min(mnid[id_v[it]],it);
    }
    remv.clear();
    perm1.clear();
    perm1.pb(SRC);
    for(auto it:mp){
        perm1.pb(it.first),++num;
    }
    perm1.pb(400);
    rep(i,V) dist[400][i]=0,dist[i][400]=0;
    VC=perm1.size();
    double curscore=0;
    int curcnt=0;
    if(perm1.size()>2){
        FOR(i,1,perm1.size()){
            curscore-=dist[perm1[i-1]][perm1[i]];
            if(turn-curscore<Tmax) curcnt+=carcnt[perm1[i]];
        }
    }
    bperm1=perm1;
    if(bperm1.size()<=3){
        bperm1.pop_back();
        bperm1.pb(0);
        return;
    }
    double bestscore=curscore+curcnt*200;
    //num=(1<<26);
    double t,start=timer.get(),ts,starttemp=30,endtemp=0.001,invtl=1.0/(25.0-start);
    int nxscore;
    while(1){
        t=timer.get();
        if(t>25){
            break;
        }
        ts=starttemp+(endtemp-starttemp)*(t-start)*invtl;
        int sz1=perm1.size();
        int id1=rnd.nextInt(sz1-2),id2=rnd.nextInt(sz1-2);
        if(id1==id2) id2=(id2+1)%(sz1-2);
        ++id1,++id2;
        if(id1>id2) swap(id1,id2);

        reverse(perm1.begin()+(id1),perm1.begin()+(id2+1));
        nxscore=0;
        curcnt=0;
        FOR(i,1,perm1.size()){
            nxscore-=dist[perm1[i-1]][perm1[i]];
            if(turn-nxscore<Tmax) curcnt+=carcnt[perm1[i]];
        }
        nxscore+=curcnt*200;

        double diff=nxscore-curscore;
		if(diff>=0||diff>LN[rnd.nextInt()&65535]*ts){
            curscore+=diff;
            
            if(bestscore<curscore){
                bestscore=curscore;
                bperm1=perm1;
            }
        }
        else{
            reverse(perm1.begin()+(id1),perm1.begin()+(id2+1));
        }
    }
    bperm1.pop_back();
    bperm1.pb(0);
}

int bpid=1;
int updateRoute(){
    if(carry.size()==0){
        bpid=INF;
        return 0;
    }
    
    if(bperm1.size()>bpid&&turn>9500&&order.size()!=0
    &&dist[bperm1[bpid]][bperm1[bpid+1]]>dist[bperm1[bpid]][0]){
        bpid=INF;
        return 0;
    }
    
    if(bperm1.size()<=bpid){
        if(turn<9500)improveRoute();
        else improveRoute2();
        //improveRoute();
        bpid=1;
        return bperm1[bpid++];
    }
    else{
        while(bperm1[bpid]!=0&&bperm1[bpid-1]==bperm1[bpid]) ++bpid;
        if(bperm1[bpid]==0){
            bpid=INF;
            return 0;
        }
        else return bperm1[bpid++];
    }
}
pdi cenord[4];
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    timer.reset();
    //input
    cin>>V>>E;
    rep(i,E){
        int ui,vi,di;
        cin>>ui>>vi>>di;
        --ui,--vi;
        G[ui].pb(vi,di);edgecost[ui][vi]=di;
        G[vi].pb(ui,di);edgecost[vi][ui]=di;
    }
    rep(i,V) cin>>F[i];
    cin>>Tmax;

    memset(dist,0x3f,sizeof(dist));
    priority_queue<pint,vector<pint>,greater<pint> > pq;
    vector<int> tmproute;
    rep(i,V){
        memset(parent,-1,sizeof(parent));
        dist[i][i]=0;
        pq.push({0,i});
        while(!pq.empty()){
            pint pi=pq.top();pq.pop();
            int t=pi.second;
            if(dist[i][t]<pi.first) continue;
            for(auto it:G[t]){
                if(dist[i][it.first]>dist[i][t]+it.second){
                    dist[i][it.first]=dist[i][t]+it.second;
                    parent[it.first]=t;
                    pq.push({dist[i][it.first],it.first});
                }
            }
        }
        int cur;
        rep(j,V){
            tmproute.clear();
            cur=j;
            tmproute.pb(cur);
            while(parent[cur]!=i){
                cur=parent[cur];
                tmproute.pb(cur);
            }
            reverse(tmproute.begin(),tmproute.end());
            route[i][j]=tmproute;
        }
    }
    double tmpm=1.0/(2.0*65536);
    rep(i,65536){
        LN[i]=log((double)i/65536+tmpm);
    }
    vector<pdi> pvtmp;
    rep(i,V){
        double ss1=0,ss2=0;
        rep(j,V){
            ss1+=dist[i][j]*dist[i][j];
            ss2+=dist[i][j];
        }
        pvtmp.pb(ss1/V-ss2*ss2,i);
    }
    sort(pvtmp.begin(),pvtmp.end(),greater<pdi>());
    int psz=pvtmp.size()/2;
    int R2=sqrt(V);
    int c1,c2,c3,c4,c5=0;
    
    while(1){
        if(c5>200) psz=pvtmp.size();
        rep(i,4) cent[i].clear();
        if(c5>30) R2=sqrt(V)/(1.0+0.1*c5/30);
        c1=-1,c2=-1,c3=-1,c4=-1;
        c1=pvtmp[rnd.nextInt(psz)].second;
        ++c5;
        rep(i,20){
            int id=pvtmp[rnd.nextInt(psz)].second;
            if(dist[c1][id]>R2*2){
                c2=id;break;
            }
        }
        if(c2==-1) continue;
        rep(i,20){
            int id=pvtmp[rnd.nextInt(psz)].second;
            if(dist[c1][id]>R2&&dist[c2][id]>R2){
                c3=id;break;
            }
        }
        if(c3==-1) continue;
        rep(i,20){
            int id=pvtmp[rnd.nextInt(psz)].second;
            if(dist[c1][id]>R2&&dist[c2][id]>R2&&dist[c3][id]>R2){
                c4=id;break;
            }
        }
        //if(c4!=-1) break;
        if(c4==-1) continue;
        swap(c2,c3);
        FOR(i,1,V){
            int td1=dist[i][c1],td2=dist[i][c2],td3=dist[i][c3],td4=dist[i][c4];
            if(td1<td2&&td1<td3&&td1<td4) cent[0].insert(i);
            else if(td2<td1&&td2<td3&&td2<td4) cent[1].insert(i);
            else if(td3<td1&&td3<td2&&td3<td4) cent[2].insert(i);
            else cent[3].insert(i);
        }
        bool brflag=true;
        rep(i,4)FOR(j,i+1,4){
            if(abs((int)cent[i].size()-(int)cent[j].size())>10+c5/10) brflag=false;
        }
        if(brflag) break;
    }
    int tc1,tc2,tc3,tc4;
    rep(i,4){
        for(auto it:cent[i]){
            cenord[i].first+=dist[0][it];
        }
        if(cent[i].size()>0)cenord[i].first/=cent[i].size();
        if(i==0)cenord[i].second=c1;
        if(i==1)cenord[i].second=c2;
        if(i==2)cenord[i].second=c3;
        if(i==3)cenord[i].second=c4;
        cent[i].clear();
    }
    sort(cenord,cenord+4);
    tc1=cenord[0].second;tc2=cenord[1].second;
    tc3=cenord[2].second;tc4=cenord[3].second;
    FOR(i,1,V){
        int td1=dist[i][tc1],td2=dist[i][tc2],td3=dist[i][tc3],td4=dist[i][tc4];
        if(td1<td2&&td1<td3&&td1<td4) cent[0].insert(i);
        else if(td2<td1&&td2<td3&&td2<td4) cent[1].insert(i);
        else if(td3<td1&&td3<td2&&td3<td4) cent[2].insert(i);
        else cent[3].insert(i);
    }
    //interact
    string verdict;
    int prev=0,nxv=0,vid=0,pos=0;
    SRC=0,DST=0;
    int initwait=10;
    bperm1.resize(1);
    deque<int> dq;
    int rordsum=0,ptrng=20;
    for(turn=0;turn<Tmax;++turn){
        cin>>Nnew;
        int nid,tdst;
        rep(i,Nnew){
            cin>>nid>>tdst;
            --tdst;
            order.insert(nid);
            id_v[nid]=tdst;
            ordtime[nid]=turn;
            ++ordcnt[tdst];
        }

        rordsum+=Nnew;
        dq.emplace_back(Nnew);
        if(dq.size()>ptrng){
            int tmp=dq.front();dq.pop_front();
            rordsum-=tmp;
        }
        p_t=(double)rordsum/ptrng;
        if(p_t>0.8) ptflag=true;
        cin>>Nput;
        rep(i,Nput){
            cin>>nid;
            order.erase(nid);
            carry.insert(nid);
            --ordcnt[id_v[nid]];
            ++carcnt[id_v[nid]];
        }
        
        if(turn<initwait) cout<<-1<<endl;
        else{

            if(edgecost[prev][nxv]!=pos){
                cout<<nxv+1<<endl;
                ++pos;
            }
            else if(nxv!=DST){
                prev=nxv;
                pos=1;
                nxv=route[SRC][DST][vid++];
                cout<<nxv+1<<endl;
            }
            else{
                SRC=DST,vid=0;
                prev=SRC;
                DST=updateRoute();
                if(SRC==0&&DST==0){
                    cout<<-1<<endl;
                    nxv=0;
                    pos=0;
                }
                else{
                    nxv=route[SRC][DST][vid++];
                    cout<<nxv+1<<endl;
                    pos=1;
                }
            }
        }

        //input info
        cin>>verdict;
        if(verdict=="NG"){
            return 1;
        }
        cin>>Nacv;
        rep(i,Nacv){
            cin>>nid;
            carry.erase(nid);
            --carcnt[id_v[nid]];
        }


    }
    return 0;
}

Measured memory_bytes: 20816