#include<bits/stdc++.h>
#include"Aoi.h"
using namespace std;
using ll=long long;
string aoi(int N,int M,int Q,int K,vector<int> A,vector<int> B,vector<ll> C,vector<int> T,vector<int> X)
{
	map<pair<int,int>,int> Mp;
	vector<int> lst(N,-1);
	vector<ll> dist(N,0x3f3f3f3f3f3f3f3f);
	dist[0]=0;
	vector<vector<pair<int,ll>>> G(N);
	vector<vector<int>> Tree(N);
	vector<int> depth(N);
	for(int i=0;i<M;i++)
	{
		Mp[make_pair(A[i],B[i])]=Mp[make_pair(B[i],A[i])]=i;
		G[A[i]].emplace_back(B[i],C[i]);
		G[B[i]].emplace_back(A[i],C[i]);
	}
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	pq.emplace(0,0);
	while(!pq.empty())
	{
		ll d=pq.top().first;
		int u=pq.top().second;
		pq.pop();
		if(dist[u]!=d) continue;
		for(auto pr:G[u])
			if(dist[pr.first]>d+pr.second)
			{
				lst[pr.first]=u;
				dist[pr.first]=d+pr.second;
				pq.emplace(d+pr.second,pr.first);
			}
	}
	for(int i=1;i<N;i++)
		Tree[lst[i]].push_back(i);
	vector<int> dfn(N),vfa(N,-1);
	int tot;
	auto dfs=[&](auto dfs,int u)->void
	{
		dfn[u]=++tot;
		for(auto v:Tree[u])
		{
			depth[v]=depth[u]+1;
			dfs(dfs,v);
		}
	};
	auto lca=[&](int u,int v)
	{
		while(u!=v)
		{
			if(depth[u]<depth[v]) swap(u,v);
			u=lst[u];
		}
		return u;
	};
	vector<int> qind(N,Q);
	for(int i=0;i<Q;i++)
		qind[T[i]]=i;
	dfs(dfs,0);
	vector<int> pool;
	for(auto x:T)
		pool.push_back(x);
	sort(pool.begin(),pool.end(),[&](int a,int b){return dfn[a]<dfn[b];});
	for(int i=1;i<T.size();i++)
		pool.push_back(lca(pool[i-1],pool[i]));
	sort(pool.begin(),pool.end());
	pool.resize(unique(pool.begin(),pool.end())-pool.begin());
	sort(pool.begin(),pool.end(),[&](int a,int b){return dfn[a]<dfn[b];});
	for(int i=1;i<pool.size();i++)
	{
		int w=lca(pool[i-1],pool[i]);
		vfa[pool[i]]=w;
	}
	sort(pool.begin(),pool.end(),[&](int a,int b)
	{
		if(qind[a]!=qind[b])
			return qind[a]<qind[b];
		return depth[a]>depth[b];
	});
	vector<int> order(N);
	for(int i=0;i<pool.size();i++)
		order[pool[i]]=i;
	vector<int> fa(Q+Q-1,Q+Q-1);
	for(int i=0;i<pool.size();i++)
		if(vfa[pool[i]]==-1)
			fa[i]=Q+Q-1;
		else
			fa[i]=order[vfa[pool[i]]];
	vector<int> vmsk(N);
	for(int i=0;i<Q;i++)
		vmsk[i]=1<<i;
	for(int i=0;i<Q+Q;i++)
		for(int j=0;j<pool.size();j++)
			if(vfa[pool[j]]!=-1)
				vmsk[fa[j]]|=vmsk[j];
	vector<int> qmsk(M);
	for(int i=0;i<Q;i++)
	{
		int v=T[i];
		while(v)
		{
			qmsk[Mp[make_pair(v,lst[v])]]|=(1<<i);
			v=lst[v];
		}
	}
	string ans;
	auto write_32=[&](int x)
	{
		for(int i=0;i<5;i++)
			ans+=(char)(48^(x>>i&1));
	};
	auto write_120bits=[&](__int128 x)
	{
		for(int i=0;i<120;i++)
			ans+=(char)(48^(x>>i&1));
	};
	__int128 val=0;
	for(int i=0;i<Q+Q-1;i++)
	{
		if(i<=Q)
			val*=(Q+Q);
		else
			val*=(Q+Q-1-i);
		if(i<Q)
			val+=fa[i];
		else
			val+=fa[i]-i-1;
	}
	write_120bits(val);
	for(auto e:X)
	{
		for(int j=0;j<pool.size();j++)
			if(vmsk[j]==qmsk[e])
				write_32(j);
		if(!qmsk[e])
			write_32(31);
	}
	return ans;
}

#include<bits/stdc++.h>
#include"Bitaro.h"
using namespace std;
using ll=long long;
void bitaro(int N,int M,int Q,int K,vector<int> A,vector<int> B,vector<ll> C,vector<int> T,vector<int> X,string s)
{
	#define pb emplace_back
	#define mp make_pair
	#define ALL(x) (x).begin(),(x).end()
	#define rALL(x) (x).rbegin(),(x).rend()
	#define srt(x) sort(ALL(x))
	#define rev(x) reverse(ALL(x))
	#define rsrt(x) sort(rALL(x))
	#define sz(x) (int)(x.size())
	#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
	#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
	#define uni(v) v.resize(unique(ALL(v))-v.begin())
	vector<int> pool;
	for(auto e:X)
	{
		pool.pb(A[e]);
		pool.pb(B[e]);
	}
	pool.pb(0);
	srt(pool);
	uni(pool);
	vector<vector<ll>> dist(sz(pool),vector<ll>(N,0x3f3f3f3f3f3f3f3f));
	vector<vector<int>> lst(sz(pool),vector<int>(N,-1));
	vector<vector<pair<int,ll>>> G(N);
	map<pair<int,int>,int> Mp;
	vector<int> called(sz(pool));
	for(int i=0;i<M;i++) if(C[i]!=-1)
	{
		Mp[mp(A[i],B[i])]=Mp[mp(B[i],A[i])]=i;
		G[A[i]].emplace_back(B[i],C[i]);
		G[B[i]].emplace_back(A[i],C[i]);
	}
	auto solve=[&](int i)
	{
		priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
		dist[i][pool[i]]=0;
		pq.emplace(0,pool[i]);
		while(!pq.empty())
		{
			ll d=pq.top().first;
			int u=pq.top().second;
			pq.pop();
			if(d!=dist[i][u]) continue;
			for(auto pr:G[u])
				if(dist[i][pr.first]>d+pr.second)
				{
					lst[i][pr.first]=u;
					dist[i][pr.first]=d+pr.second;
					pq.emplace(d+pr.second,pr.first);
				}
		}
	};
	vector<int> fa(Q+Q-1);
	int P=0;
	auto read_32=[&]()
	{
		int ans=0;
		for(int i=0;i<5;i++)
			ans|=(48^s[P++])<<i;
		return ans;
	};
	auto read_120bits=[&]()
	{
		__int128 ans=0;
		for(int i=0;i<120;i++)
			ans|=((__int128)(48^s[P++]))<<i;
		return ans;
	};
	__int128 val=read_120bits();
	for(int i=Q+Q-2;i>=0;i--)
	{
		if(i>=Q)
			fa[i]=i+1+val%(Q+Q-1-i);
		else
			fa[i]=val%(Q+Q);
		if(i>Q)
			val/=(Q+Q-i-1);
		else
			val/=(Q+Q);
	}
	vector<int> vmsk(Q+Q);
	for(int i=0;i<Q;i++)
		vmsk[i]=(1<<i);
	for(int i=0;i<Q+Q;i++)
		for(int j=0;j<Q+Q-1;j++)
			vmsk[fa[j]]|=vmsk[j];
	vector<vector<int>> vh(Q);
	for(int i=0;i<K;i++)
	{
		int msk=read_32();
		if(msk==31) continue;
		cerr<<vmsk[msk]<<endl;
		for(int j=0;j<Q;j++)
			if(vmsk[msk]>>j&1)
				vh[j].pb(X[i]);
	}
	int indd=0;
	for(auto v:T)
	{
		vector<int> ans;
		int cur=0;
		vector<int> have=vh[indd++];
		vector<int> vis(sz(have));
		vector<int> path;
		for(int i=1;i<=sz(have);i++)
		{
			int ind=lb(pool,cur);
			if(!called[ind])
			{
				called[ind]=1;
				solve(ind);
			}
			int mxp=-1;
			for(int j=0;j<sz(have);j++)
				if(!vis[j])
					if(mxp==-1||dist[ind][mxp]>dist[ind][A[have[j]]])
						mxp=A[have[j]];
			for(int j=0;j<sz(have);j++)
				if(!vis[j])
					if(mxp==-1||dist[ind][mxp]>dist[ind][B[have[j]]])
						mxp=B[have[j]];
			int tmp=mxp;
			while(tmp!=cur)
			{
				path.pb(Mp[mp(tmp,lst[ind][tmp])]);
				tmp=lst[ind][tmp];
			}
			rev(path);
			for(auto e:path)
				ans.pb(e);
			for(int j=0;j<sz(have);j++) if(!vis[j])
			{
				if(A[have[j]]==mxp)
				{
					cur=B[have[j]];
					vis[j]=1;
					ans.pb(have[j]);
				}
				else if(B[have[j]]==mxp)
				{
					cur=A[have[j]];
					vis[j]=1;
					ans.pb(have[j]);
				}
			}
			path.clear();
		}
		int ind=lb(pool,cur);
		if(!called[ind])
		{
			called[ind]=1;
			solve(ind);
		}
		int tmp=v;
		while(tmp!=cur)
		{
			path.pb(Mp[mp(tmp,lst[ind][tmp])]);
			tmp=lst[ind][tmp];
		}
		rev(path);
		for(auto e:path)
			ans.pb(e);
		answer(ans);
	}
	return ;
}