#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<int,int>P;

std::chrono::system_clock::time_point start;
std::chrono::system_clock::time_point owari;

unsigned long long xor128() {
    static unsigned long long rx = 411111789, ry = 9471111169, rz = 5212488629, rw = 886575123;
    unsigned long long rt = (rx ^ (rx << 11));
    rx = ry;
    ry = rz;
    rz = rw;
    return (rw = (rw ^ (rw >> 19)) ^ (rt ^ (rt >> 8)));
}
 
double rand128(double min = 0, double max = 1){
        return (double)(xor128() % 0xFFFF) / 0xFFFF * (max - min) + min;
}

double calc_time(){
	owari = std::chrono::system_clock::now();
	return std::chrono::duration_cast<std::chrono::milliseconds>(owari-start).count();
}
int XXX;
int MMM=10;
bool NO[5000];
int dp[1<<20][20];
P pre[1<<20][20];

struct Graph{
	int n,m,T_max;
	int dist[400][400];
	int query[10000];
	vector<int>id[10000];
	vector<int>ver[10000];
	vector<P>G[400];
	int nexT[400][400];
	vector<int>NEX[400][400];
	vector<int>TSP;
	unordered_map<int,int>id_conf;
	int f[400];
	Graph(){}
	void init(){
		for(int i=0;i<400;i++){
			for(int j=0;j<400;j++){
				dist[i][j] = i==j?0:1e8;
				nexT[i][j] = j;
			}
		}
		cin>>n>>m;
		for(int i=0;i<m;i++){
			int a,b;
			double c;
			cin>>a>>b>>c; a--; b--;
			if(a==0)XXX=b;
			if(b==0)XXX=a;
			dist[a][b]=dist[b][a]= ceil(c);
		}
		r(i,n)cin>>f[i];
		cin>>T_max;
		/*
		r(i,T_max){
			cin>>query[i];
			r(j,query[i]){
				MMM=min(i,MMM);
				int a,b;
				cin>>a>>b; b--;
				id[i].emplace_back(a);
				ver[i].emplace_back(b);
				id_conf[a]=i;
			}
		}
		*/
	}
	void warshall(){
		for(int k=0;k<n;k++){
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					if(dist[i][j] > dist[i][k]+dist[k][j]){
						dist[i][j] = dist[i][k]+dist[k][j];
						nexT[i][j] = nexT[i][k];
					}
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				for(int cur=i;cur!=j;cur=nexT[cur][j]){
					NEX[i][j].emplace_back(cur);
				}
				NEX[i][j].emplace_back(j);
				if( i==j )NEX[i][j].emplace_back(j);
			}
		}
		r(i,n){
			//cerr<<dist[0][i]<<' '<<i<<endl;
		}
	}
	void Aneeling(){
		vector<int>v,ANS;
		set<int>used;
		int now=0;
		v.emplace_back(0);
		used.insert(0);
		int MAX=1e9,cur=0;
		r(i,n-1){
			int MIN=1e9,ID;
			r(j,n)if(!used.count(j)){
				if(dist[now][j]<MIN){
					MIN=dist[now][j];
					ID=j;
				}
			}
			//ID=i+1;
			cur+=MIN;
			v.emplace_back(ID);
			used.insert(ID);
			now=ID;
		}
		cur+=dist[v[n-1]][0];


		double startTemp=0;
	    double endTemp=0;
	    int cnt=0;
		// 焼きなす
		const double saTimeStart    = calc_time();         // 焼きなまし開始時刻。getTimeは、時間を返す関数
	    const double saTimeEnd      = 15000;
		while(1){
			double ela = calc_time();
			if( ela > 23000 )break;
			vector<int>nex(n);
			int i=xor128()%n;
			int j=xor128()%n;
			int k=xor128()%n;
			if(k<j)swap(k,j);
			if(j<i)swap(j,i);
			if(k<j)swap(k,j);
			if(!i)continue;
			if(i==j||j==k)continue;
			int e=xor128()%4,X=0;
			int sco = cur;

			if(e==0){
				sco -= dist[v[i-1]][v[i]];
				sco -= dist[v[j-1]][v[j]];
				if(k!=n-1)sco -= dist[v[k+1]][v[k]];
				else sco -= dist[0][v[k]];
				sco += dist[v[i-1]][v[k]];
				sco += dist[v[j]][v[i]];
				if(k!=n-1)sco += dist[v[j-1]][v[k+1]];
				else sco += dist[0][v[j-1]];
			}
			if(e==1){
				sco -= dist[v[i-1]][v[i]];
				sco -= dist[v[j-1]][v[j]];
				if(k!=n-1)sco -= dist[v[k+1]][v[k]];
				else sco -= dist[0][v[k]];
				sco += dist[v[i-1]][v[j-1]];
				sco += dist[v[i]][v[k]];
				if(k!=n-1)sco += dist[v[j]][v[k+1]];
				else sco += dist[0][v[j]];
			}
			if(e==2){
				sco -= dist[v[i-1]][v[i]];
				sco -= dist[v[j-1]][v[j]];
				if(k!=n-1)sco -= dist[v[k+1]][v[k]];
				else sco -= dist[0][v[k]];
				sco += dist[v[i-1]][v[j]];
				sco += dist[v[k]][v[j-1]];
				if(k!=n-1)sco += dist[v[i]][v[k+1]];
				else sco += dist[0][v[i]];
			}
			if(e==3){
				sco -= dist[v[i-1]][v[i]];
				sco -= dist[v[j-1]][v[j]];
				if(k!=n-1)sco -= dist[v[k+1]][v[k]];
				else sco -= dist[0][v[k]];
				sco += dist[v[i-1]][v[k]];
				sco += dist[v[j]][v[j-1]];
				if(k!=n-1)sco += dist[v[i]][v[k+1]];
				else sco += dist[0][v[i]];
			}

			/*int AX=cur;
        	int BX=sco;
			double TT = saTimeEnd-saTimeStart;
	        double t = calc_time()-saTimeStart; 
	        double temp = startTemp + (endTemp - startTemp) * t / TT;
	        double prob = exp(( -BX+AX ) / temp);
	        bool FORCE_NEXT = prob > (double)rand128(0,1) ;*/

			if(cur >= sco){
				if(e==0){
					r(a,i) nex[X++]=(v[a]);
					for(int a=k;a>=j;a--) nex[X++]=(v[a]);
					for(int a=i;a<j;a++) nex[X++]=(v[a]);
					for(int a=k+1;a<n;a++) nex[X++]=(v[a]);
				}
				if(e==1){
					r(a,i) nex[X++]=(v[a]);
					for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
					for(int a=k;a>=j;a--) nex[X++]=(v[a]);
					for(int a=k+1;a<n;a++) nex[X++]=(v[a]);
				}
				if(e==2){
					r(a,i) nex[X++]=(v[a]);
					for(int a=j;a<k+1;a++) nex[X++]=(v[a]);
					for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
					for(int a=k+1;a<n;a++) nex[X++]=(v[a]);
				}
				if(e==3){
					r(a,i) nex[X++]=(v[a]);
					for(int a=k;a>=j;a--) nex[X++]=(v[a]);
					for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
					for(int a=k+1;a<n;a++) nex[X++]=(v[a]);
				}
				//if(X!=n)cout<<X<<endl;
	        	cur = sco;
				v = nex;

	        }

	        if(MAX > sco){
	        	MAX = sco;
	        	ANS = nex;
	        	//cout<<i<<' '<<j<<' '<<k<<endl;
	        	//cout<<MAX<<' '<<n<<' '<<cnt++<<' '<<nex.size()<<endl;
	        }

	        cnt++;
		}
		TSP=ANS;
		int sco=0;
		r(i,n){
			if(i!=n-1)sco+=dist[ANS[i]][ANS[i+1]];
			else sco+=dist[0][ANS[n-1]];
		}
		/*
		r(i,n){
			int cnt=0;
			if(i)r(j,NEX[TSP[i-1]][TSP[i]].size()){
				if(NEX[TSP[i-1]][TSP[i]][j]==0)cnt=1;
			}
			if(i)cerr<<dist[0][TSP[i]]<<' '<<dist[TSP[i-1]][TSP[i]]<<' '<<TSP[i-1]<<' '<<TSP[i]<<' '<<cnt<<endl;
		}
		*/
		//cout<<sco<<endl;
	}

	void Aneeling_2(){
		vector<int>v,ANS;
		set<int>used;
		int now=0;
		v.emplace_back(0);
		used.insert(0);
		int MAX=1e9,cur=0;
		r(i,n-1){
			int MIN=1e9,ID;
			r(j,n)if(!used.count(j)){
				if(dist[now][j]<MIN){
					MIN=dist[now][j];
					ID=j;
				}
			}
			//ID=i+1;
			cur+=MIN;
			v.emplace_back(ID);
			if(n/2==i)v.emplace_back(0);
			used.insert(ID);
			now=ID;
		}
		v.emplace_back(0);
		cur+=dist[v[n-1]][0];


		double startTemp=0;
	    double endTemp=0;
	    int cnt=0;
		// 焼きなす
		const double saTimeStart    = calc_time();         // 焼きなまし開始時刻。getTimeは、時間を返す関数
	    const double saTimeEnd      = 15000;
		while(1){
			double ela = calc_time();
			if( ela > 25000 )break;
			vector<int>nex(n+2);
			int i=xor128()%(n+2);
			int j=xor128()%(n+2);
			int k=xor128()%(n+2);
			if(k<j)swap(k,j);
			if(j<i)swap(j,i);
			if(k<j)swap(k,j);
			if(!i)continue;
			if(i==j||j==k)continue;
			int e=xor128()%4,X=0;


			if(e==0){
				r(a,i) nex[X++]=(v[a]);
				for(int a=k;a>=j;a--) nex[X++]=(v[a]);
				for(int a=i;a<j;a++) nex[X++]=(v[a]);
				for(int a=k+1;a<n+2;a++) nex[X++]=(v[a]);
			}
			if(e==1){
				r(a,i) nex[X++]=(v[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k;a>=j;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+2;a++) nex[X++]=(v[a]);
			}
			if(e==2){
				r(a,i) nex[X++]=(v[a]);
				for(int a=j;a<k+1;a++) nex[X++]=(v[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+2;a++) nex[X++]=(v[a]);
			}
			if(e==3){
				r(a,i) nex[X++]=(v[a]);
				for(int a=k;a>=j;a--) nex[X++]=(v[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+2;a++) nex[X++]=(v[a]);
			}

			/*int AX=cur;
        	int BX=sco;
			double TT = saTimeEnd-saTimeStart;
	        double t = calc_time()-saTimeStart; 
	        double temp = startTemp + (endTemp - startTemp) * t / TT;
	        double prob = exp(( -BX+AX ) / temp);
	        bool FORCE_NEXT = prob > (double)rand128(0,1) ;*/

			int sco = 0,TRU;
			vector<int>vec;
			r(i,n+2){
				if(nex[i]==0)vec.emplace_back(i);
				if(i!=n+1)sco+=dist[nex[i]][nex[i+1]];
				else sco+=dist[nex[i]][0];
			}
			TRU=sco;
			vec.emplace_back(n+2);

			sco -= abs(vec[0]-vec[1])*abs(vec[1]-vec[2])*abs(vec[2]-vec[3])*0.0001;
			if(vec[0]+1==vec[1])sco += 10000;
			if(vec[1]+1==vec[2])sco += 10000;
			if(vec[2]+1==vec[3])sco += 10000;

			if(cur >= sco){
				//if(X!=n)cout<<X<<endl;
	        	cur = sco;
				v = nex;

	        }

	        if(MAX > sco){
	        	MAX = sco;
	        	ANS = nex;
	        	//cout<<vec[0]<<' '<<vec[1]<<' '<<vec[2]<<' '<<vec[3]<<endl;
	        	//cout<<TRU<<endl;
	        	//cout<<i<<' '<<j<<' '<<k<<endl;
	        	//cout<<MAX<<' '<<n<<' '<<cnt++<<' '<<nex.size()<<endl;
	        }

	        cnt++;
		}
		TSP=ANS;
		int sco=0;
		r(i,n){
			if(i!=n-1)sco+=dist[ANS[i]][ANS[i+1]];
			else sco+=dist[0][ANS[n-1]];
		}
		/*
		r(i,n){
			int cnt=0;
			if(i)r(j,NEX[TSP[i-1]][TSP[i]].size()){
				if(NEX[TSP[i-1]][TSP[i]][j]==0)cnt=1;
			}
			if(i)cerr<<dist[0][TSP[i]]<<' '<<dist[TSP[i-1]][TSP[i]]<<' '<<TSP[i-1]<<' '<<TSP[i]<<' '<<cnt<<endl;
		}
		*/
		//cout<<sco<<endl;
	}

	void Aneeling_3(){
		vector<int>v,ANS;
		set<int>used;
		int now=0;
		v.emplace_back(0);
		used.insert(0);
		int MAX=1e9,cur=0;
		r(i,n-1){
			int MIN=1e9,ID;
			r(j,n)if(!used.count(j)){
				if(dist[now][j]<MIN){
					MIN=dist[now][j];
					ID=j;
				}
			}
			//ID=i+1;
			cur+=MIN;
			v.emplace_back(ID);
			if(n/2==i)v.emplace_back(0);
			used.insert(ID);
			now=ID;
		}
		//v.emplace_back(0);
		cur+=dist[v[n-1]][0];


		double startTemp=0;
	    double endTemp=0;
	    int cnt=0;
		// 焼きなす
		const double saTimeStart    = calc_time();         // 焼きなまし開始時刻。getTimeは、時間を返す関数
	    const double saTimeEnd      = 15000;
		while(1){
			double ela = calc_time();
			if( ela > 25000 )break;
			vector<int>nex(n+1);
			int i=xor128()%(n+1);
			int j=xor128()%(n+1);
			int k=xor128()%(n+1);
			if(k<j)swap(k,j);
			if(j<i)swap(j,i);
			if(k<j)swap(k,j);
			if(!i)continue;
			if(i==j||j==k)continue;
			int e=xor128()%4,X=0;


			if(e==0){
				r(a,i) nex[X++]=(v[a]);
				for(int a=k;a>=j;a--) nex[X++]=(v[a]);
				for(int a=i;a<j;a++) nex[X++]=(v[a]);
				for(int a=k+1;a<n+1;a++) nex[X++]=(v[a]);
			}
			if(e==1){
				r(a,i) nex[X++]=(v[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k;a>=j;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+1;a++) nex[X++]=(v[a]);
			}
			if(e==2){
				r(a,i) nex[X++]=(v[a]);
				for(int a=j;a<k+1;a++) nex[X++]=(v[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+1;a++) nex[X++]=(v[a]);
			}
			if(e==3){
				r(a,i) nex[X++]=(v[a]);
				for(int a=k;a>=j;a--) nex[X++]=(v[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+1;a++) nex[X++]=(v[a]);
			}
// 29,27,26,25
			/*int AX=cur;
        	int BX=sco;
			double TT = saTimeEnd-saTimeStart;
	        double t = calc_time()-saTimeStart; 
	        double temp = startTemp + (endTemp - startTemp) * t / TT;
	        double prob = exp(( -BX+AX ) / temp);
	        bool FORCE_NEXT = prob > (double)rand128(0,1) ;*/

			int sco = 0,TRU;
			vector<int>vec;
			r(i,n+1){
				if(nex[i]==0)vec.emplace_back(i);
				if(i!=n)sco+=dist[nex[i]][nex[i+1]];
				else sco+=dist[nex[i]][0];
			}
			TRU=sco;
			vec.emplace_back(n+1);

			sco -= abs(vec[0]-vec[1])*abs(vec[1]-vec[2])*0.01;
			if(vec[0]+1==vec[1])sco += 10000;
			if(vec[1]+1==vec[2])sco += 10000;
			//if(vec[2]+1==vec[3])sco += 10000;

			if(cur >= sco){
				//if(X!=n)cout<<X<<endl;
	        	cur = sco;
				v = nex;

	        }

	        if(MAX > sco){
	        	MAX = sco;
	        	ANS = nex;
	        	//cout<<vec[0]<<' '<<vec[1]<<' '<<vec[2]<<' '<<vec[3]<<endl;
	        	//cout<<TRU<<endl;
	        	//cout<<i<<' '<<j<<' '<<k<<endl;
	        	//cout<<MAX<<' '<<n<<' '<<cnt++<<' '<<nex.size()<<endl;
	        }

	        cnt++;
		}
		TSP=ANS;
		int sco=0;
		r(i,n){
			if(i!=n-1)sco+=dist[ANS[i]][ANS[i+1]];
			else sco+=dist[0][ANS[n-1]];
		}
		/*
		r(i,n){
			int cnt=0;
			if(i)r(j,NEX[TSP[i-1]][TSP[i]].size()){
				if(NEX[TSP[i-1]][TSP[i]][j]==0)cnt=1;
			}
			if(i)cerr<<dist[0][TSP[i]]<<' '<<dist[TSP[i-1]][TSP[i]]<<' '<<TSP[i-1]<<' '<<TSP[i]<<' '<<cnt<<endl;
		}
		*/
		//cout<<sco<<endl;
	}

	int TSP_dp(vector<int>&A,vector<int>&B,int kakikae=1){
		int N=A.size();
		vector<int>tmp=A;
		r(i,1<<N)r(j,N)dp[i][j]=1e9;
		r(i,N)dp[1<<i][i]=dist[0][A[i]];//,cerr<<(1<<i)<<i<<dist[0][A[i]]<<endl;;
		//cerr<<<<endl;
		r(i,1<<N){
			r(j,N){
				if(dp[i][j]==1e9)continue;
				r(k,N){
					if(i&(1<<k))continue;
					int nex=i|(1<<k);
					if(dp[nex][k] > dp[i][j]+dist[A[j]][A[k]]){
						dp[nex][k] = dp[i][j]+dist[A[j]][A[k]];
						pre[nex][k] = P(i,j);
					}
				}
			}
		}
		//cerr<<dp[1][0]<<endl;
		int S=(1<<N)-1,ID,MAX=1e9;
		r(i,N){
			//cerr<<S<<' '<<i<<' '<<dp[S][i]<<endl;
			if(MAX>dp[S][i]+dist[A[i]][0]){
				MAX = dp[S][i]+dist[A[i]][0];
				ID = i;
			}
		}
		if(!kakikae)return MAX;
		//cerr<<ID<<endl;
		A.clear();
		A.emplace_back(tmp[ID]);
		r(i,N-1){
			P p=pre[S][ID];
			S=p.first;
			ID=p.second;
			//cerr<<S<<' '<<ID<<endl;
			A.emplace_back(tmp[ID]);
		}
		//cerr<<N<<endl;
		//exit(0);

		return MAX;
	}

	int next_vertex(int A,int B){
		int x=NEX[A][B][1];
		//cout<<A<<' '<<B<<' '<<x<<endl;
		return x;
	}

	vector<int> Inter_ract(){
		vector<int>ope;
		long long score = 0;

		unordered_set<int>have[400];
		unordered_set<int>store[400];
		int tim=0,dir=0,now=0,nex=0,A=0,B,zero=0;
		vector<int> lis;

		r(i,T_max){
			//cout<<i<<endl;

			//continue;
			//if(i>=10)break;
			//cerr<<i<<endl;
			//cout<<now<<' '<<nex<<' '<<A<<' '<<B<<' '<<i<<endl;
			//if(i>=1000)break;
			int iku=0;

			cin>>query[i];
			r(j,query[i]){
				//cout<<endl;
				MMM=min(i,MMM);
				int a,b;
				cin>>a>>b; b--;
				id[i].emplace_back(a);
				ver[i].emplace_back(b);
				id_conf[a]=i;
			}

			int get;
			cin>>get;
			r(i,get){
				int p;
				cin>>p;
			}
			string s;
			//cin>>s;
			//cout<<s<<endl;
			//exit(0);
			//cout<<query[i]<<' '<<get<<endl;

			if( query[i] ) {
				//cout<<i<<endl;
				store[ver[i][0]].insert(id[i][0]);
				//exit(0);
			}

			if( now == 0 && A == 0 ){
				zero=0;
				//lis.clear();
				nex=0;
				r(j,400){
					for(auto &e:store[j]){
						have[j].insert(e);
					}
					store[j].clear();
				}
				int cnt = 0;
				vector<int>v,ID;
				//v.emplace_back(0);
				r(j,400)if((int)have[j].size()){
					cnt++;
					v.emplace_back(j);
					ID.emplace_back(*have[j].begin());
				}
				//vector<int>VV(1);
				//return VV;
				//exit(1);
				//cout<<cnt<<endl;
				if( cnt==0 ){
					//cout<<i<<endl;
					cout<<-1<<endl;
					string ok;
					cin>>ok;
					if(ok=="NG"){
						vector<int>VV(1);
						return VV;
					}
					//cout<<ok<<endl;
					int get2;
					cin>>get2;
					r(i,get2){
						int p;
						cin>>p;
					}
					//ope.emplace_back(-1);
					continue;
				}
				else if(cnt<=18 && (int)lis.size()==0){
					//cout<<i<<endl;
					//cout<<(int)v.size()<<' '<<v[0]<<endl;
					int score = TSP_dp(v,ID);
					//cout<<(int)v.size()<<' '<<v[0]<<endl;
					//cout<<endl;
					//exit(0);
					v.emplace_back(0);
				}
				else if( (int)lis.size()==0){
					v = TSP;
					v.erase(v.begin());
					
						//v.insert(v.begin()+n/3,0);
						//v.insert(v.begin()+n/3+n/3,0);
					
					v.emplace_back(0);
				}
				
				if((int)lis.size()==0){
					lis = v;
					nex = next_vertex(now,lis[0]);
					//cout<<lis[0]<<lis[1]<<endl;
					A=0;
					B=dist[now][nex];
				}
				else{
					nex = next_vertex(now,lis[0]);
					//cout<<lis[0]<<lis[1]<<endl;
					A=0;
					B=dist[now][nex];
				}

			}

			else if( A==0 && zero==0 ){
				for(auto &e:have[now]){
					int pre=id_conf[e];
					score += 100000000 - (i-pre)*(i-pre);
				}
				have[now].clear();
				
				int cnt=0;
				vector<int>v,v1,v2;
				r(i,400){
					if((int)have[i].size())cnt++,v.emplace_back(i),v1.emplace_back(i);
					if((int)store[i].size())cnt++,v.emplace_back(i),v2.emplace_back(i);
				}
				sort(v.begin(),v.end());
				v.erase(unique(v.begin(),v.end()),v.end());
				cnt=(int)v.size();

				if(0 && cnt<=18&&(int)v2.size()){
					int X=TSP_dp(v2,v2,0);
					//cerr<<i<<endl;
					r(i,lis.size()){
						if(!i)X+=dist[0][lis[0]];
						else X+=dist[lis[i-1]][lis[i]];
					}
					int Y=dist[now][0]+TSP_dp(v,v,0);
					//cerr<<X<<' '<<Y<<' '<<dist[now][0]<<endl;
					if(X>Y){
						TSP_dp(v,v);
						v.insert(v.begin(),0);
						lis = v;
						lis.clear();
						lis.emplace_back(0);
						nex = next_vertex(now,lis[0]);
						A=0;
						B=dist[now][nex];
						zero=1;
					}
				}
				
			}
			//cout<<now<<' '<<nex<<' '<<A<<' '<<B<<' '<<i<<endl;
			//ope.emplace_back(nex);
			if(now==nex)cout<<(int)lis.size()<<endl;
			else cout<<nex+1<<endl;
			//cout<<endl;
			string ok;
			cin>>ok;
			if(ok=="NG"){
						vector<int>VV(1);
						return VV;
					}
			int get2;
			cin>>get2;
			r(i,get2){
				int p;
				cin>>p;
			}
			A++;
			B--;
			//cout<<now<<' '<<nex<<' '<<A<<' '<<B<<' '<<i<<' '<<lis.size()<<endl;

			if( B==0 ){
				now = nex;
				//cout<<nex<<' '<<lis[0]<<' '<<lis[1]<<endl;
				if( (int)lis.size() && now == lis[0] )lis.erase(lis.begin());
				if( (int)lis.size() && now == lis[0] )lis.erase(lis.begin());
				//if( (int)lis.size() && now == lis[0] )lis.erase(lis.begin());
				if((int)lis.size())nex = next_vertex(now,lis[0]);
				//cout<<nex<<endl;
				//if( lis.size() && nex == lis[0] )lis.erase(lis.begin());
				A=0;
				B=dist[now][nex];
			}

			//cerr<<i<<endl;
			//cout<<now<<' '<<nex<<' '<<A<<' '<<B<<' '<<i<<endl;

		}
		//cout<<ope.size()<<endl;

		//return ope;
		//cerr<< score <<endl;
		//exit(0);
		/*
		r(i,T_max){
			if(ope[i]==-1)cout<<ope[i]<<endl;
			else cout<<ope[i]+1<<endl;
		}
		*/

		vector<int>V(n);
		return V;


	}

	long long simulation(vector<int> &A){

		long long score = 0;
		memset(NO,0,sizeof(NO));

		unordered_set<int>have[400];
		unordered_set<int>store[400];
		int tim=0,cnt=0,now=1;

		r(i,A.size()){
			//cerr<<i<<endl;
			//cout<<A[i]<<' '<<A[i+1]<<' '<<i<<' '<<A.size()<<endl;
			if(A[i]!=-1 && A[i+1]!=0&&have[A[i+1]].size()==0)NO[i+1]=1;

			r(j,NEX[A[i]][A[i+1]].size()-1){

				int s=NEX[A[i]][A[i+1]][j];
				int t=NEX[A[i]][A[i+1]][j+1];
				//cout<<'a'<<endl;
				r(k,dist[s][t]){
					if(cnt==T_max){
						//cerr<<i<<
						return score;
					}
					if(query[cnt]){
						if(id[cnt].size()==0)exit(0);
						store[ver[cnt][0]].insert(id[cnt][0]);
					}
					cnt++;
				}
				//cout<<'b'<<endl;
				
				for(auto &e:have[t]){
					//cout<<e<<endl;
					int pre=id_conf[e];
					score += 100000000 - (cnt-pre)*(cnt-pre);
				}
				have[t].clear();
				if(t==0){
					r(k,400){
						for(auto &e:store[k]){
							have[k].insert(e);
						}
						store[k].clear();
					}
				}
			}
			//cout<<score<<endl;
		}

		return score;
	}
	long long output(vector<int> &A){

		long long score = 0;

		unordered_set<int>have[400];
		unordered_set<int>store[400];
		int tim=0,cnt=0,now=1;

		if(query[cnt]){
			if(id[cnt].size()==0)exit(0);
			store[ver[cnt][0]].insert(id[cnt][0]);
		}

		r(i,A.size()){
			//cout<<A[i]<<' '<<A[i+1]<<' '<<i<<' '<<A.size()<<endl;

			r(j,NEX[A[i]][A[i+1]].size()-1){

				int s=NEX[A[i]][A[i+1]][j];
				int t=NEX[A[i]][A[i+1]][j+1];
				//cout<<'a'<<endl;
				r(k,dist[s][t]){
					if(cnt==T_max) return score;
					cout<<t+1<<endl;
					cnt++;
					if(query[cnt]){
						if(id[cnt].size()==0)exit(0);
						store[ver[cnt][0]].insert(id[cnt][0]);
					}
				}
				//cout<<'b'<<endl;
				
				for(auto &e:have[t]){
					//cout<<e<<endl;
					int pre=id_conf[e];
					score += 100000000 - (cnt-pre)*(cnt-pre);
				}
				have[t].clear();
				if(t==0){
					r(k,400){
						for(auto &e:store[k]){
							have[k].insert(e);
						}
						store[k].clear();
					}
				}
			}
			//cout<<score<<endl;
		}

		return score;
	}
};



int main(){
	start = std::chrono::system_clock::now();
	Graph G;
	G.init();
	G.warshall();

	if(G.n>=260)G.Aneeling_2();
	else G.Aneeling_3();
	vector<int>v=G.Inter_ract();

	if(v.size()==1)return 1;

	return 0;

	int i=0;
	int cnt=0;

	vector<int>Z;
	r(i,MMM/G.dist[0][XXX]+1){
		Z.emplace_back(0);
		Z.emplace_back(XXX);
	}
	while((int)Z.size()<=4500){
		r(j,G.TSP.size())Z.emplace_back(G.TSP[j]);
	}

	long long T=G.simulation(Z),MAX=0;

	for(int i=0;i<100000;i++){
		if(calc_time()>=29900)break;
		int e=xor128()%4;
		if(e==0){
			long long TMP=G.simulation(Z);

			int x;
			while(1){
				x=xor128()%3000+1;
				if(NO[x])break;;
			}
			int r=x;
			while(NO[r])r++;
			while(x && NO[x])x--; x++;

			vector<int> t;
			r(k,r-x)t.emplace_back(Z[k+x]);
			//cerr<<x<<' '<<r<<' '<<Z.size()<<' '<<r-x<<endl;
			Z.erase(Z.begin()+x,Z.begin()+r);
			long long N=G.simulation(Z);
			//cerr<<x<<' '<<r<<' '<<Z.size()<<endl;
			if(N>=T){
				T=N;
				//cout<<T<<' '<<i<<' '<<Z.size()<<endl;
				if(Z.size()<=4000){
					cerr<<endl;
					r(j,G.TSP.size())Z.emplace_back(G.TSP[j]);
				}
			}
			else{
				Z.insert(Z.begin()+x,t.begin(),t.end());
				//if(Z[x]!=t)exit(0);
			}
			if(MAX<N){
				MAX=N;
				cerr<<N<<' '<<i<<' '<<calc_time()<<' '<<Z.size()<<' '<<1<<endl;
			}
		}
		else if(e==1){
			int x=xor128()%3000+1;
			while(Z[x]!=0)x++;x++;
			int r=x;
			while(Z[r]!=0)r++;
			reverse(Z.begin()+x,Z.begin()+r);
			long long N=G.simulation(Z);
			//cerr<<x<<' '<<r<<' '<<Z.size()<<endl;
			if(N>=T){
				T=N;
			}
			else{
				reverse(Z.begin()+x,Z.begin()+r);
				//if(Z[x]!=t)exit(0);
			}
			if(MAX<N){
				MAX=N;
				cerr<<N<<' '<<i<<' '<<calc_time()<<' '<<Z.size()<<' '<<2<<endl;
			}
		}
		else if(e==2){
			int x=xor128()%3000+1;
			Z.insert(Z.begin()+x,0);
			long long N=G.simulation(Z);
			//cerr<<x<<' '<<r<<' '<<Z.size()<<endl;
			if(N>=T){
				T=N;
			}
			else{
				Z.erase(Z.begin()+x);
				//if(Z[x]!=t)exit(0);
			}
			if(MAX<N){
				MAX=N;
				cerr<<N<<' '<<i<<' '<<calc_time()<<' '<<Z.size()<<' '<<3<<endl;
			}
		}
		else if(e==3){
			vector<int>zer;
			r(i,Z.size())if(i<3000&&Z[i]==0)zer.emplace_back(i);
			int x=zer[xor128()%(int)zer.size()];
			Z.insert(Z.begin()+x,XXX);
			Z.insert(Z.begin()+x,0);
			long long N=G.simulation(Z);
			//cerr<<x<<' '<<r<<' '<<Z.size()<<endl;
			if(N>=T){
				T=N;
			}
			else{
				Z.erase(Z.begin()+x);
				Z.erase(Z.begin()+x);
				//if(Z[x]!=t)exit(0);
			}
			if(MAX<N){
				MAX=N;
				cerr<<N<<' '<<i<<' '<<calc_time()<<' '<<Z.size()<<' '<<4<<endl;
			}
		}
		//cerr<<x<<' '<<r<<' '<<Z.size()<<endl;
	}

	cerr<<G.simulation(Z)<<endl;
	cerr<<Z[0]<<endl;
	G.output(Z);

}

Measured memory_bytes: 53068