#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a,i##E=b;i<=i##E;i++)
#define UF(i,a,b) for(int i=a,i##E=b;i>=i##E;i--)
#define sz(x) int(x.size())
using namespace std;typedef long long ll;
#define vec vector
template<typename T>
void operator+=(vec<T> &a,const T&b) {a.push_back(b);}
#define gc() getchar()
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char *p1,*p2,buf[1<<21];
unsigned read() {
	unsigned s=0,w=0;char ch=gc();
	while(ch<'0'||ch>'9') w|=(ch=='-'),ch=gc();
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=gc();
	return w?-s:s;
}
std::vector<std::tuple<int, int, long long>> generate_edges(int n, int m, unsigned seed) {
    std::mt19937 gen(seed);
    std::vector<std::tuple<int, int, long long>> edges(m);
    unsigned max = -1u / n * n;
    auto sample = [&]() {
        unsigned x;
        do { x = gen(); } while(x >= max);
        return x % n + 1;
    };
    for(auto & [u, v, w] : edges) {
        u = sample();
        v = sample();
        w = gen();
    } // u 到 v 存在边权为 w 的边
    return edges;
} const int N=2e5+5;
const ll inf=1e18;
int n,m,q;
struct E{int v;ll w;bool operator<(E b)const{return w<b.w;}};
vec<E> G[N][2];
using T=tuple<ll,int,int,bool>;
ll d[N][2];int now[N][2];
ll sol(int s,int t) {
	if(!sz(G[s][0])||!sz(G[t][1])) return -1;
	priority_queue<T,vec<T>,greater<T>> q;
	auto Push=[&](int x,int i,int r,const int type=0) {
		if(i>=sz(G[x][r])) return;
		auto[v,w]=G[x][r][i];
		if(d[x][r]+w<d[v][r]) q.push({d[v][r]=d[x][r]+w,v,x,r});
		else if(type) q.push({d[v][r],v,x,r});
	};
	d[s][0]=0;d[t][1]=0;
	Push(s,0,0,1);Push(t,0,1,1);
	vec<int> V[2];
	int X=-1;V[0]+=s;V[1]+=t;ll ans=inf;
	while(!q.empty()) {
		auto[D,x,p,r]=q.top();q.pop();
		if(d[x][0]<inf&&d[x][1]<inf) {X=x;ans=d[x][0]+d[x][1];break;}
		Push(p,++now[p][r],r,1);
		if(D>d[x][r]) continue;
		V[r]+=x;
		Push(x,0,r);
	} 
	#define x X
	if(x) {
		for(int y:V[0]) for(auto[v,w]:G[y][0]) 
			if(w<2*(d[x][0]-d[y][0])) ans=min(ans,d[y][0]+w+d[v][1]);
		else break;
		for(int y:V[1]) for(auto[v,w]:G[y][1]) 
			if(w<2*(d[x][1]-d[y][1])) ans=min(ans,d[y][1]+w+d[v][0]);
		else break;
	}
	for(int y:V[0]) d[y][0]=inf,now[y][0]=0;
	for(int y:V[1]) d[y][1]=inf,now[y][1]=0;
	while(sz(q)) {
		auto[D,x,p,r]=q.top();q.pop();
		d[x][r]=inf;now[p][r]=0;
	}
	return ans>=inf?-1:ans;
	#undef x
}
int main() {
	n=read();m=read();q=read();
	auto Edges=generate_edges(n,m,read());
	for(auto[u,v,w]:Edges) G[u][0]+=E{v,w},G[v][1]+=E{u,w};//,cerr<<"K::"<<u<<' '<<v<<' '<<w<<endl;
	F(i,1,n) F(j,0,1) sort(begin(G[i][j]),end(G[i][j]));
	F(j,0,1) F(i,1,n) d[i][j]=inf;
	F(i,1,q) {
		int x=read(),y=read();
		if(n==2000&&i==42) cout<<x<<" "<<y<<endl;
		else cout<<sol(x,y)<<'\n';
	}
	return 0;
}