#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> YAMANOBORI(vector<int>&A,vector<int>&B,int K){
		map<int,int>M;
		r(i,(int)A.size()){
			M[A[i]]=B[i];
		}

		int N=min(n/4,(int)A.size());
		if(K>=9200){
			N=A.size();
		}
		else{
			while(N>10 && 3*N+K>=9400)N--;
		}


		vector<P>vec;
		r(i,(int)A.size()){
			vec.emplace_back(P(B[i],i));
		}
		sort(vec.begin(),vec.end(),greater<P>());

		vector<long long>vA,vB;
		vector<int>ANS,idx;
		set<int>used;
		int now=0;
		long long MAX=1e18,cur=0,sum=0;
		r(i,A.size()){
			vA.emplace_back(vec[i].second);
			vB.emplace_back(vec[i].first);
		}
		r(i,N){
			
			idx.emplace_back(i);
			ANS.emplace_back(i);
			//cout<<i<<endl;
		}

		r(i,N){
			int MIN=1e9,ID;
			r(j,N)if(!used.count(j)){
				if(dist[now][A[vA[j]]]<MIN){
					MIN=dist[now][A[vA[j]]];
					ID=j;
				}
			}
			//ID=i+1;
			cur+=MIN;
			idx.emplace_back(ID);
			//if(n/2==i)v.emplace_back(0);
			used.insert(ID);
			now=ID;
		}
		now=0;

		r(i,N){
			cur += dist[now][A[vA[idx[i]]]];
			now = A[vA[idx[i]]];
		}
		if(K<9500-n)cur += dist[0][A[idx[N-1]]];
		MAX=cur;
		//cur += dist[0][A[vA[N-1]]]*10;
		//cur += (sum*sum);
		//cout<<cur<<' '<<A.size()<<' '<<N<<endl;
		vector<int>nex(N);

		int TT=8000000;
		//if(K>=9500-n)TT*=2;
		//if(N<13)TT/=10;


		if(A.size()>=3){
		if(K<9200)for(int iteration = 0;iteration<TT;iteration++){

			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==0)continue;
			if(i==j||j==k)continue;

			int e=xor128()%4,X=0;

			long long sco = cur,now=0,sum=0;

			if(e==0){
				if(i)sco -= dist[A[vA[idx[i-1]]]][A[vA[idx[i]]]];
				else sco -= dist[0][A[vA[idx[i]]]];
				sco -= dist[A[vA[idx[j-1]]]][A[vA[idx[j]]]];
				if(k!=N-1)sco -= dist[A[vA[idx[k+1]]]][A[vA[idx[k]]]];
				else if(K<9500-n)sco -= dist[0][A[vA[idx[k]]]];
				if(i)sco += dist[A[vA[idx[i-1]]]][A[vA[idx[k]]]];
				else sco += dist[0][A[vA[idx[k]]]];
				sco += dist[A[vA[idx[j]]]][A[vA[idx[i]]]];
				if(k!=N-1)sco += dist[A[vA[idx[j-1]]]][A[vA[idx[k+1]]]];
				else sco += dist[0][A[vA[idx[j-1]]]];
			}

			
			if(e==1){
				if(i)sco -= dist[A[vA[idx[i-1]]]][A[vA[idx[i]]]];
				else sco -= dist[0][A[vA[idx[i]]]];
				sco -= dist[A[vA[idx[j-1]]]][A[vA[idx[j]]]];
				if(k!=N-1)sco -= dist[A[vA[idx[k+1]]]][A[vA[idx[k]]]];
				else if(K<9500-n)sco -= dist[0][A[vA[idx[k]]]];
				if(i)sco += dist[A[vA[idx[i-1]]]][A[vA[idx[j-1]]]];
				else sco += dist[0][A[vA[idx[j-1]]]];
				sco += dist[A[vA[idx[i]]]][A[vA[idx[k]]]];
				if(k!=n-1)sco += dist[A[vA[idx[j]]]][A[vA[idx[k+1]]]];
				else sco += dist[0][A[vA[idx[j]]]];
			}
			
			if(e==2){
				if(i)sco -= dist[A[vA[idx[i-1]]]][A[vA[idx[i]]]];
				else sco -= dist[0][A[vA[idx[i]]]];
				sco -= dist[A[vA[idx[j-1]]]][A[vA[idx[j]]]];
				if(k!=N-1)sco -= dist[A[vA[idx[k+1]]]][A[vA[idx[k]]]];
				else if(K<9500-n)sco -= dist[0][A[vA[idx[k]]]];
				if(i)sco += dist[A[vA[idx[i-1]]]][A[vA[idx[j]]]];
				else sco += dist[0][A[vA[idx[j]]]];
				sco += dist[A[vA[idx[k]]]][A[vA[idx[j-1]]]];
				if(k!=n-1)sco += dist[A[vA[idx[i]]]][A[vA[idx[k+1]]]];
				else if(K<9500-n)sco += dist[A[vA[idx[i]]]][0];
			}
			
			if(e==3){
				if(i)sco -= dist[A[vA[idx[i-1]]]][A[vA[idx[i]]]];
				else sco -= dist[0][A[vA[idx[i]]]];
				sco -= dist[A[vA[idx[j-1]]]][A[vA[idx[j]]]];
				if(k!=N-1)sco -= dist[A[vA[idx[k+1]]]][A[vA[idx[k]]]];
				else if(K<9500-n)sco -= dist[0][A[vA[idx[k]]]];
				if(i)sco += dist[A[vA[idx[i-1]]]][A[vA[idx[k]]]];
				else sco += dist[0][A[vA[idx[k]]]];
				sco += dist[A[vA[idx[j]]]][A[vA[idx[j-1]]]];
				if(k!=n-1)sco += dist[A[vA[idx[i]]]][A[vA[idx[k+1]]]];
				else if(K<9500-n)sco += dist[A[vA[idx[i]]]][0];
			}
/*

			if(e==0){
				r(a,i) nex[X++]=(idx[a]);
				for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
				for(int a=i;a<j;a++) nex[X++]=(idx[a]);
				for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
			}
			if(e==1){
				r(a,i) nex[X++]=(idx[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(idx[a]);
				for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
				for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
			}
			if(e==2){
				r(a,i) nex[X++]=(idx[a]);
				for(int a=j;a<k+1;a++) nex[X++]=(idx[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(idx[a]);
				for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
			}
			if(e==3){
				r(a,i) nex[X++]=(idx[a]);
				for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
				for(int a=j-1;a>=i;a--) nex[X++]=(idx[a]);
				for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
			}
			r(a,N){
				sco += (long long)dist[now][A[vA[nex[a]]]];
				now = A[vA[nex[a]]];
			}
			sco += (long long)dist[0][A[vA[nex[N-1]]]];
*/
			if(cur >= sco){
				if(e==0){
					r(a,i) nex[X++]=(idx[a]);
					for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
					for(int a=i;a<j;a++) nex[X++]=(idx[a]);
					for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
				}
				if(e==1){
					r(a,i) nex[X++]=(idx[a]);
					for(int a=j-1;a>=i;a--) nex[X++]=(idx[a]);
					for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
					for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
				}
				if(e==2){
					r(a,i) nex[X++]=(idx[a]);
					for(int a=j;a<k+1;a++) nex[X++]=(idx[a]);
					for(int a=j-1;a>=i;a--) nex[X++]=(idx[a]);
					for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
				}
				if(e==3){
					r(a,i) nex[X++]=(idx[a]);
					for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
					for(int a=j-1;a>=i;a--) nex[X++]=(idx[a]);
					for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
				}
	        	cur = sco;
				idx = nex;

	        }

	        if(MAX > sco){
	        	/*
	        	if(e==0){
					r(a,i) nex[X++]=(idx[a]);
					for(int a=k;a>=j;a--) nex[X++]=(idx[a]);
					for(int a=i;a<j;a++) nex[X++]=(idx[a]);
					for(int a=k+1;a<N;a++) nex[X++]=(idx[a]);
				}*/
	        	MAX = sco;
	        	ANS = nex;
	        }

		}

		else{
			//cout<<K<<endl;
			TT=1000000000;
			cur=MAX=0;
			int SUM=1e9;
//cout<<11111<<endl;
			for(int iteration = 0;iteration<TT;iteration++){

				if(iteration%100==0){
					if(calc_time()>=29900)break;
				}

			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==0)continue;
			if(i==j||j==k)continue;

			int e=xor128()%4,X=0;

			long long sco =0,now=0,sum=0;

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

		r(a,N){
			sum+=dist[now][A[vA[nex[a]]]];
			if(sum+K<10000)sco++;
			now = A[vA[nex[a]]];
		}

			if(cur < sco || cur==sco&&sum<SUM){
	        	cur = sco;
	        	SUM=sum;
				idx = nex;

	        }

	        if(MAX < sco){
	        	MAX = sco;
	        	ANS = nex;
	        }

		}
		}

		}
		else return A;

		//if(A.size()==360)exit(1);

		vector<int>ret;
		r(i,N){
			ret.emplace_back(A[vA[ANS[i]]]);
		}
		if(K>=9200){
			//cout<<MAX<<endl;
			return ret;
		}
		//cout<<A.size()<<' '<<ret.size()<<endl;
		//cout<<MAX<<endl<<endl;

		int X=N;
		
		for(;X<(int)A.size();X++){
			vector<P>v;

			v.emplace_back( P(-dist[0][ret[0]]+(dist[0][A[vA[X]]]+dist[A[vA[X]]][ret[0]]),0) );
			for(int i=0;i<N-1;i++){
				v.emplace_back(P(-dist[ret[i+1]][ret[i]]+(dist[ret[i+1]][A[vA[X]]]+dist[A[vA[X]]][ret[i]]),i+1));
			}
			v.emplace_back( P(-dist[0][ret[N-1]]+(dist[0][A[vA[X]]]+dist[A[vA[X]]][ret[N-1]]),N) );
			sort(v.begin(),v.end());

			if(v[0].first <= 2){
				//cout<<v[0].first<<' '<<v[0].second<<endl;
				ret.insert(ret.begin()+v[0].second,A[vA[X]]);
				N++;
				//cout<<N<<' '<<A[X]<<endl;
			}
		}
if(1){
		int sA=0,sB=0,suA=0,suB=0,AA=0,BB=0;
		now=0;
		r(a,N){
			sA += (long long)dist[now][ret[a]];
			//if(K+sA>=10000)continue;
			suA += (sA+M[ret[a]])*(sA+M[ret[a]]);
			now = ret[a];
			AA++;
		}
		reverse(ret.begin(),ret.end());
		now=0;suA=0;
		r(a,N){
			sA += (long long)dist[now][ret[a]];
			//if(K+sA>=10000)continue;
			suB += (sA+M[ret[a]])*(sA+M[ret[a]]);
			now = ret[a];
			BB++;
		}
		if(BB<AA)reverse(ret.begin(),ret.end());
		else if(suB>suA)reverse(ret.begin(),ret.end());

		if(AA==BB && sA+K>=9250)
		{

		int sA=0,sB=0,suA=0,suB=0,AA=0,BB=0;
		now=0;
		r(a,N){
			sA += (long long)dist[now][ret[a]];
			if(a && K+sA>=9250){
				ret.erase(ret.begin()+a,ret.end());
				break;
			}
			suA += (sA+M[ret[a]])*(sA+M[ret[a]]);
			now = ret[a];
			AA++;
		}

		}
}
		

		return ret;
	}

	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){

			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;

			if( query[i] ) {
				store[ver[i][0]].insert(id[i][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);
					int p=0;
					for(auto &e:have[j]){
						p+=(i - id_conf[e])*(i - id_conf[e]);//*(f[j]);
					}
					//p*=f[j];
					ID.emplace_back(p);
				}
				//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{
					v = YAMANOBORI(v,ID,i);
					//cerr<<v.size()<<endl;
					v.emplace_back(0);
				}
				if(1){
					lis = v;
					r(j,v.size()-1){
						if(v[j]==v[j+1])cout<<1111<<endl;
					}
					nex = next_vertex(now,lis[0]);
					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();
			}

			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 ){
				//if((int)lis.size()>=2&&lis[0]==lis[1])cout<<lis[0]<<lis[1]<<endl;
				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: 23124