#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 LEN=0;
	int CNT=0;
	int n,m,T_max;
	int dist[400][400];
	int query[10000];
	vector<int>id[10000];
	vector<int>ver[10000];
	vector<P>G[400];
	unordered_set<int>have[400];
	unordered_set<int>store[400];
	int nexT[400][400];
	vector<int>NEX[400][400];
	vector<int>TSP[4];
	unordered_map<int,int>id_conf;
	unordered_set<int>SSS[4];
	int TSP_N;
	int f[400];

	Graph(){}

	int T_peak=0;

	void calc_T_peak(int K){
		int sum[10000];
		memset(sum,0,sizeof(sum));
		r(i,K+1)sum[i] = query[i];
		r(i,K)sum[i+1] += sum[i];
		vector<P>v;
		for(int i=200;i<K-200;i++){
			v.emplace_back(P(sum[i+200]-sum[i-200],i));
		}
		sort(v.begin(),v.end(),greater<P>());
		r(i,100){
		//	//cerr<<v[i].first<<' '<<v[i].second<<endl;
		}
		//exit(1);
		T_peak = v[0].second;
		if(T_peak>K-300){
			//T_peak += 500;
			vector<P>v2;
			r(i,(int)v.size()){
				v2.emplace_back(P(abs((double)v[i].first-200),v[i].second));
			}
			sort(v2.begin(),v2.end());
			int idx=v2[0].second;
			T_peak = min(9500,idx*2);
			//r(i,100)cerr<<i<<' '<<v2[i].second<<endl;
			//cerr<<T_peak<<' '<<idx<<endl;
			//exit(1);
		}
		//cerr<<T_peak<<endl;
		//exit(1);
	}

	double COST(int RANG,int K,vector<int>v){
		double X=(int)v.size();
		set<int>st,SS;

		int nn=n;
		int cn=0;
		unordered_map<int,int>UN,NU;

		r(i,n){
			nn++;
			if(f[i]==2){
				UN[i] = cn+n;
				NU[cn+n] = UN[i];
				cn++;
				nn++;
			}
		}
		r(i,(int)v.size()){
			if( f[i]==2 ){
					SS.insert(UN[i]);
				}
			SS.insert(v[i]);
		}

		r(i,n){
			if((int)have[i].size() && !SS.count(i)){
				st.insert(i);
				if( f[i]==2 ){
					st.insert(UN[i]);
				}
			}
			if((int)store[i].size()){
				st.insert(i);
				if( f[i]==2 ){
					st.insert(UN[i]);
				}
			}
		}

		double num  = (int)st.size();
		double score = (int)st.size();
		double TA=9500;
		if(T_peak==9500)TA+=0.1;
		for(int i=K;i<=min(RANG,9500);i++){
			score += (1.0 - num/nn) * ((TA-i)/(TA-T_peak));
			num += (1.0 - num/nn) * ((TA-i)/(TA-T_peak));
		}

		double cost = (double)LEN/n +(nn/score - 1 )/1.54747 ;
		double l=0,r=score;
		//cerr<<score<<' '<<RANG<<' '<<cost<<' '<<K<<endl;
		double XX=(10000.0-RANG);
		r(i,50){
			double mid=(l+r)/2;
			if( mid*cost < XX ) l=mid;
			else r=mid;
		}
		score = l;
		//cerr<<X<<' '<<score<<endl<<X+score<<endl<<endl;
		//exit(1);

		return X + score;
	}

	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_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/3==i)v.emplace_back(0);
			if(n/3+n/3==i)v.emplace_back(0);
			used.insert(ID);
			now=ID;
		}
		v.emplace_back(0);
		v.emplace_back(0);
		cur+=dist[v[n-1]][0];


		double startTemp=0.5;
	    double endTemp=0;
	    int cnt=0;

	    int len=0;
	    r(i,n+3){
	    	len += dist[v[i]][v[i+1]];
	    }
	    vector<int>z;
	    r(i,n+4){
	    	if(v[i]==0)z.emplace_back(i);
	    }

		// 焼きなす
		const double saTimeStart    = calc_time();         // 焼きなまし開始時刻。getTimeは、時間を返す関数
	    const double saTimeEnd      = 15000;
		while(1){
			for(int e=0;e<2;e++)
			for(int i=1;i<n+3;i++)
			for(int k=i+1;k<n+3;k++){
				if(e && i+1==k)continue;
				//cerr<<len<<endl;
			double ela = calc_time();
			if( ela > 15000 )goto LLL;
			//vector<int>nex(n+3);

			if(!i)continue;
			//if(i==j||j==k)continue;
			//int e=xor128()%3,
			int X=0;
			int nex=len;
			vector<int>zz=z;

			if(e==0){
				nex -= dist[v[i]][v[i-1]];
				nex -= dist[v[k]][v[k+1]];
				nex += dist[v[k]][v[i-1]];
				nex += dist[v[i]][v[k+1]];
				/*
				r(a,i) nex[X++]=(v[a]);
				for(int a=k;a>=i;a--) nex[X++]=(v[a]);
				//for(int a=j-1;a>=i;a--) nex[X++]=(v[a]);
				for(int a=k+1;a<n+3;a++) nex[X++]=(v[a]);
				*/
				r(a,(int)zz.size()){
					if(i<=zz[a]&&zz[a]<=k){
						zz[a] = i + abs(k-zz[a]);
					}
				}
				sort(zz.begin(),zz.end());
			}
			//cerr<<len<<endl;

			if(e==1){
				//r(a,n+3)nex[a]=v[a];
				int L=i;
				int R=k;
				nex -= dist[v[i]][v[i-1]];
				nex -= dist[v[i]][v[i+1]];
				nex -= dist[v[k]][v[k-1]];
				nex -= dist[v[k]][v[k+1]];
				nex += dist[v[i]][v[k-1]];
				nex += dist[v[i]][v[k+1]];
				nex += dist[v[k]][v[i-1]];
				nex += dist[v[k]][v[i+1]];
				r(a,(int)zz.size()){
					if(i==zz[a]){
						zz[a] = k;
					}
					else if(k==zz[a]){
						zz[a] = i;
					}
				}
				sort(zz.begin(),zz.end());
				//while(R==L)R=xor128()%(n+3);
				//swap(v[L],v[R]);
			}
/*
			if(e==2){
				r(a,n+3)nex[a]=v[a];
				int L=i;
				int R=k;
				//while(R==L)R=xor128()%(n+3);
				int TMP=nex[L];
				nex.erase(nex.begin()+L);
				nex.insert(nex.begin()+R,TMP);

			}
*/

			int sco = nex,TRU=nex;


			TRU=sco;
			//cerr<<zz.size()<<endl;
			//vec.emplace_back(n+3);

			sco -= (long long)abs(zz[0]-zz[1])*abs(zz[1]-zz[2])*abs(zz[2]-zz[3])*abs(zz[3]-zz[4])/sco/sco*n;
			if(abs(zz[0]-zz[1])<20)sco += 10000;
			if(abs(zz[1]-zz[2])<20)sco += 10000;
			if(abs(zz[2]-zz[3])<20)sco += 10000;
			if(abs(zz[3]-zz[4])<20)sco += 10000;
			//cerr<<len<<' '<<nex<<' '<<sco<<endl;

			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||FORCE_NEXT){
				//if(X!=n)cout<<X<<endl;
	        	cur = sco;
	        	len = nex;
	        	z = zz;
	        	if(e==0) reverse(v.begin()+i,v.begin()+k+1);
	        	else swap(v[i],v[k]);
	        }

	        if(MAX > sco){
	        	MAX = sco;
	        	ANS = v;
	        	//cerr<<zz[0]<<' '<<zz[1]<<' '<<zz[2]<<' '<<zz[3]<<' '<<zz[4]<<' '<<e<<' '<<cnt<<endl;
	        	//cerr<<len<<' '<<calc_time()<<' '<<cnt<<endl;
	        	LEN = len;
	        	//cout<<i<<' '<<j<<' '<<k<<endl;
	        	//cout<<MAX<<' '<<n<<' '<<cnt++<<' '<<nex.size()<<endl;
	        }
	        cnt++;
		}}
		LLL:;
		vector<int>Z;
		//ANS.emplace_back(0);
		int idd=0;
		r(i,(int)ANS.size()){
			if(ANS[i]==0){
				if(i){
					r(a,(int)Z.size()){
						SSS[idd].insert(Z[a]);
					}
					TSP[idd++]=Z;
					////cerr<<TSP[idd-1].size()<<endl;
				}
				Z.clear();
			}
			else{
				Z.emplace_back(ANS[i]);
			}
		}
		//exit(0);
		TSP_N=idd;
		////cerr<<idd<<endl;
		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 next_vertex(int A,int B){
		int x=NEX[A][B][1];
		//cout<<A<<' '<<B<<' '<<x<<endl;
		return x;
	}

	int CNT2=0;

	int IDX(vector<int>&A){
		for(int k=1,l=0;l<4;l++,k++){
			////cerr<<k<<endl;
			int sum=0;
			r(j,TSP[(CNT2+k)%TSP_N].size()){
				r(i,(int)A.size()){
					if(TSP[(CNT2+k)%TSP_N][j]==A[i]) sum++;
				}
			}
			if(sum){
				////cerr<<sum<<endl;
				CNT2 = (CNT2+k)%TSP_N;
				return CNT2;
			}
		}
	}

	vector<int> NEX_TSP(vector<int>&A,int C){
		vector<int>nex;
		r(i,TSP[C].size()){
			int F=0;
			r(j,A.size()){
				if(TSP[C][i]==A[j]){
					F=1;
					break;
				}
			}
			if(F){
				nex.emplace_back(TSP[C][i]);
			}
		}
		return nex;
	}

	vector<int> YAMANOBORI(vector<int>&A,vector<int>&B,int K,vector<int>&C){

		map<int,int>M;
		r(i,(int)A.size()){
			M[A[i]]=B[i];
		}

		int N=min(n/4,(int)A.size());
		vector<int>v;
		vector<long long>vA,vB;
		vector<int>ANS,idx;
		set<int>used;
		int now=0;
		long long MAX=1e18,cur=0,sum=0;
		////cerr<<K<<endl;

		if(K<9500-LEN/4+LEN/16){
			int idx2 = IDX(A);
			v=NEX_TSP(A,idx2);
			N=v.size();
			//r(i,n)used.insert(v[i]);

			vector<int>idx=v;
			int now=0;
			r(i,N){
				cur+=dist[now][idx[i]];
				now=idx[i];
			}
			cur+=dist[now][0];
			MAX=cur;

			int TT=100000;
			////cerr<<MAX<<' '<<cur<<endl;
			if( N>2){
				
				////cerr<<K<<endl;
				for(int iteration = 0;iteration<TT;iteration++){
					////cerr<<iteration<<endl;
					////cerr<<MAX<<' '<<cur<<endl;

					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;
					////cerr<<i<<j<<k<<' '<<idx.size()<<endl;
					if(i==j||j==k)continue;

					int e=0,X=0;

					long long sco = cur,now=0,sum=0;
					if(e==0){
						if(i)sco -= dist[idx[i-1]][idx[i]];
						else sco -= dist[0][idx[i]];
						sco -= dist[idx[j-1]][idx[j]];
						if(k!=N-1)sco -= dist[idx[k+1]][idx[k]];
						else sco -= dist[0][idx[k]];
						if(i)sco += dist[idx[i-1]][idx[k]];
						else sco += dist[0][idx[k]];
						sco += dist[idx[j]][idx[i]];
						if(k!=N-1)sco += dist[idx[j-1]][idx[k+1]];
						else sco += dist[0][idx[j-1]];
					}

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

					if(cur >= sco){
						vector<int>nex(N);
						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){
			        	MAX = sco;
			        	//cerr<<MAX<<endl;
			        	v = idx;
			        }
		        }
	    	}
	    	r(a,N){
	    		used.insert(v[a]);
	    	}
	    	{
	    	for(int qq=0;qq<3;qq++){
				for(int p=1;p>=0;p--){
					for(int X=0;X<(int)A.size();X++){
						if(used.count(A[X]))continue;
						vector<P>v2;

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

						if(v2[0].first <= p){
							v.insert(v.begin()+v2[0].second,A[X]);
							N++;
							used.insert(A[X]);
						}
					}
				}
//99173573
//
				for(int p=3;p>=0;p--){
					for(int X=0;X<(int)A.size();X++){
						if(used.count(A[X]))continue;
						if( !SSS[(idx2-1+4)%4].count(A[X]) )continue;
						vector<P>v2;

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

						if(v2[0].first <= p){
							v.insert(v.begin()+v2[0].second,A[X]);
							N++;
							used.insert(A[X]);
						}
					}
				}
			}
			}

			int RANG=K;now=0;
	    	r(a,N){
	    		RANG += (long long)dist[now][v[a]];
				now = v[a];
	    	}
	    	RANG += dist[0][now];

	    	if( 9500-LEN/4+LEN/16 <=RANG){

	    		calc_T_peak(K);
	    		////cerr<<K<<' '<<T_peak<<endl;
		    	double score_1 = COST(RANG,K,v);

		    	while( 9500-LEN/4+LEN/16 <=RANG){
		
		    		int flag=0;
		    		int RR=-1;
		    		for(int p=0;p<=15;p++){
						for(int X=0;X<(int)A.size();X++){
							if(used.count(A[X]))continue;
							vector<P>v2;

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

							if(v2[0].first <= p){
								v.insert(v.begin()+v2[0].second,A[X]);
								N++;
								used.insert(A[X]);
								flag=1;
								RR=v2[0].second;
								goto L;
							}
						}
					}
					L:;
					if(!flag)break;
					RANG=K,now=0;
			    	r(a,N){
			    		RANG += (long long)dist[now][v[a]];
						now = v[a];
			    	}
			    	RANG += dist[0][now];
			    	double score_2 = COST(RANG,K,v);
			    	////cerr<<score_1<<' '<<score_2<<endl;

			    	if(score_1 > score_2){
			    		v.erase(v.begin()+RR);
			    		N--;
			    		break;
			    	}
			    	else{
			    		score_1 = score_2;
			    	}
		    	}
//exit(1);
		    	//r(i,2000)//cerr<<RANG<<' '<<K<<endl;

	    	}
	    	//exit(0);



			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][v[a]];
						suA += (sA+M[v[a]])*(sA+M[v[a]]);
						now = v[a];
						AA++;
					}
					reverse(v.begin(),v.end());
					now=0;sA=0;
					r(a,N){
						sA += (long long)dist[now][v[a]];
						//if(K+sA>=10000)continue;
						suB += (sA+M[v[a]])*(sA+M[v[a]]);
						now = v[a];
						BB++;
					}
					if(BB<AA)reverse(v.begin(),v.end());
					else if(suB>suA)reverse(v.begin(),v.end());
			}

			return v;
		}
		else{
			//cerr<<K<<endl;
			N=A.size();
			////cerr<<N<<endl;
			r(i,A.size()){
				vA.emplace_back(i);
				vB.emplace_back(B[i]);
				/*
				idx.emplace_back(i);
				ANS.emplace_back(i);
				*/
			}
			r(i,N){
				////cerr<<i<<endl;
				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;
					}
				}
				cur+=MIN;
				idx.emplace_back(ID);
				used.insert(ID);
				now=ID;
				ANS.emplace_back(ID);
			}
			////cerr<<N<<endl;

			now=0;
			cur=0;

			r(i,N){
				sum += dist[now][A[vA[idx[i]]]];
				if(sum+K<10000)cur += C[i];
				now = A[vA[idx[i]]];
			}
			MAX=cur;
			////cerr<<cur<<endl;
			//exit(1);
		}

		////cerr<<N<<' '<<v.size()<<' '<<A.size()<<endl;
		//cur += dist[0][A[vA[N-1]]]*10;
		//cur += (sum*sum);
		//cout<<cur<<' '<<A.size()<<' '<<N<<endl;
		vector<int>nex(N);

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


		if(A.size()>=3){
		if(K<9500-LEN/4+LEN/16)for(int iteration = 0;iteration<TT;iteration++){
			break;
			////cerr<<iteration<<endl;

			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;
			////cerr<<i<<j<<k<<' '<<idx.size()<<endl;
			if(i==j||j==k)continue;

			int e=0,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]);
			}
			*/

			////cerr<<i<<j<<k<<endl;
			////cerr<<idx[0]<<idx[1]<<idx[2]<<endl;
			if(cur >= sco){
				////cerr<<idx[0]<<idx[1]<<idx[2]<<endl;
				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;
	        	long long sco2=0;
			r(a,N){
				sco2 += (long long)dist[now][A[vA[nex[a]]]];
				now = A[vA[nex[a]]];
			}
			sco2 += (long long)dist[0][A[vA[nex[N-1]]]];
			////cerr<<sco<<' '<<sco2<<endl;
	        }
		}

		else{
			////cerr<<K<<endl;
			double TIM=29300;
			TIM+=CNT*600;
			CNT++;
			if(TIM>29900){
				TIM=29910;
			}
			TT=1000000000;
			//cur=MAX=0;
			////cerr<<cur<<' '<<MAX<<endl;
			//exit(1);
			int SUM=1e9;
			for(int iteration = 0;iteration<TT;iteration++){

				if(iteration%100==0){
					if(calc_time()>=TIM)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()%5,X=0;
			//cerr<<e<<endl;

			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]);
			}
			if(e==4){
				//cerr<<e<<' '<<e<<' '<<N<<' '<<v.size()<<' '<<nex.size()<<endl;
				r(a,N)nex[a]=idx[a];
				//cerr<<e<<' '<<e<<endl;
				int L=xor128()%(N);
				int R=xor128()%(N);
				//cerr<<L<<' '<<R<<endl;
				int TMP=nex[L];
				nex.erase(nex.begin()+L);
				nex.insert(nex.begin()+R,TMP);
				//cerr<<nex.size()<<' '<<e<<endl;
			}
		//int p=0;
			r(a,N){
				sum+=dist[now][A[nex[a]]];
				if(sum+K<10000)sco+=C[nex[a]];
				//p+=C[a];
				now = A[nex[a]];
			}
			////cerr<<N<<' '<<sco<<' '<<p<<endl;

			if(cur < sco || cur==sco&&sum<=SUM){
				////cerr<<sco<<' '<<sum+K<<' '<<A.size()<<endl;
	        	cur = sco;
	        	SUM=sum;
				idx = nex;

	        }

	        if(MAX < sco){
	        	cerr<<MAX<<' '<<calc_time()<<' '<<e<<'\n';
	        	MAX = sco;
	        	ANS = nex;
	        	////cerr<<MAX<<' '<<calc_time()<<endl;
	        }

		}
		}

		}
		else return A;

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

		vector<int>ret;
		r(i,N){
			ret.emplace_back(A[vA[ANS[i]]]);
		}
		if(K>=9500-LEN/4+LEN/16){
			return ret;
		}
		else ret=v;
		return ret;
		//cout<<A.size()<<' '<<ret.size()<<endl;
		//cout<<MAX<<endl<<endl;

		int X=N,TM=X;
		set<int>ss;

/*
		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++;
				ss.insert(X);
				//cout<<N<<' '<<A[X]<<endl;
			}
		}
*/
		

		return ret;
	}

long long TTT;
	vector<int> Inter_ract(){
		vector<int>ope;
		long long score = 0,S1=0,S2=0;
		long long SSS = 0;

		int tim=0,dir=0,now=0,nex=0,A=0,B,zero=0; 
// 99059416
// 98914443
// 99458389
// 
		vector<int> lis;

		r(i,T_max){
			if(i==8500){
				TTT=S1/S2;
				cerr<<TTT<<endl;
				//exit(1);
			}

			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;
			}

			string s;

			if( query[i] ) {
				store[ver[i][0]].insert(id[i][0]);
			}

			if( now == 0 && A == 0 &&(int)lis.size()==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,NUM;
				//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]);
					}
					//if(i>=8000)p/=f[j];
					ID.emplace_back(p);
					NUM.emplace_back((int)have[j].size());
				}
				//vector<int>VV(1);
				//return VV;
				//exit(1);
				//cout<<cnt<<endl;
				if( cnt==0 ){
					//cout<<i<<endl;
					cout<<-1<<endl;

					//ope.emplace_back(-1);
					continue;
				}
				else{
					v = YAMANOBORI(v,ID,i,NUM);
					////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 ){

				if(now==0){
					r(j,400){
						for(auto &e:store[j]){
							have[j].insert(e);
						}
						store[j].clear();
					}
				}
				else{
					for(auto &e:have[now]){
						int pre=id_conf[e];
						score += 100000000 - (i-pre)*(i-pre);
						if(i>=3000)S1+=100000000 - (i-pre)*(i-pre),S2++;
						SSS++;
					}
					have[now].clear();
				}
			}

			if(now==nex)cout<<(int)lis.size()<<endl;
			else cout<<nex+1<<endl;
			//cout<<endl;

			A++;
			B--;
			if( B==0 ){
				now = nex;
				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]);
				A=0;
				B=dist[now][nex];
			}

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

};



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

	//if(G.n>=260)G.Aneeling_2();
	G.Aneeling_2();
	//exit(0);
	vector<int>v=G.Inter_ract();
	//cerr<<G.TTT<<endl;
	//cerr<<G.T_peak<<endl;

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

	return 0;


}


Measured memory_bytes: 23424