#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;
bool NO[5000];

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;
	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);
		}
		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);
			}
		}
	}
	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 > 15000 )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]];
		}
		//cout<<sco<<endl;
	}

	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()){
			//cout<<A[i]<<' '<<A[i+1]<<' '<<i<<' '<<A.size()<<endl;
			if(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();

	G.Aneeling();
	//exit(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: 25472