求调

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e4+5;
const int M=2e4+5;
template<typename type>
inline void read(type &x){
	x=0;
	bool flag=0;
	char ch=getchar();
	while(!isdigit(ch)){
		flag=ch=='-';
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	flag?x=-x:0;
}
struct edge{
	int to,val,next;
}e[2*M];
int n,m,q,cnt,k,fcnt,A,B;
int h1[N],h2[N];
int dfn[N],low[N];
int fa[N],fid[N],fval[N];
int sc[N],sq[N];
int f[N][15],dep[N],dis[N];
void addedge(int head[],int u,int v,int val){
	cnt++;
	e[cnt].to=v;
	e[cnt].val=val;
	e[cnt].next=head[u];
	head[u]=cnt;
}
void pre(){
	for(int j=1;j<=15;j++){
		for(int i=1;i<=fcnt;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
}
void dfs(int u,int fa){
//	for(int i=h[u];i;i=e[i].next){
//		int y=e[i].to;
//		if(y==f[u][0]) continue;
//		f[y][0]=u;
//		dis[y]=dis[u]+e[i].val;
//		dep[y]=dep[u]+1;
//		dfs(y);		
//	}
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=15;i++) f[u][i]=f[f[u][i-1]][i-1];
	
	for(int i=h2[u];i;i=e[i].next){
		int y=e[i].to;
		if(y!=fa){			
			dis[y]=dis[u]+e[i].val;
			dfs(y,u);
		}
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=15;i>=0;i--){
		if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	}
	if(u==v) return u;
	for(int i=15;i>=0;i--){
		if(f[u][i]!=f[v][i])
			u=f[u][i],v=f[v][i];
	}
	A=u,B=v;
	return f[u][0];
}
void build(int u,int v,int val){
	int sum=val;
	for(int i=v;i!=u;i=fa[i]){
		sq[i]=sum;
		sum+=fval[i];
	}
	sq[u]=sc[u]=sum;
	addedge(h2,u,++fcnt,0);
	for(int i=v;i!=u;i=fa[i]){
		sc[i]=sum;
		addedge(h2,fcnt,i,min(sq[i],sum-sq[i]));
	}
}
void tarjan(int u,int ine){
	dfn[u]=low[u]=++k;
	for(int i=h1[u];i;i=e[i].next){
		int y=e[i].to;
		if(!dfn[y]){
			fa[y]=u,fval[y]=e[i].val,fid[y]=i;
			tarjan(y,i);
			low[u]=min(low[u],low[y]);
			if(dfn[u]<low[y]){
//				printf("ccc\n");
				addedge(h2,u,y,e[i].val);
			}				
		}
		else if(i!=(ine^1)){
//			printf("2:%d\n",low[u]);
			low[u]=min(low[u],dfn[y]);
		}		
	}
	for(int i=h1[u];i;i=e[i].next){
		int y=e[i].to;
		if(dfn[u]<dfn[y]&&fid[y]!=i)
			build(u,y,e[i].val);
	}
}

int main(){
	read(n),read(m),read(q);
	for(int i=1;i<=m;i++){
		int u,v,w;
		read(u),read(v),read(w);
		addedge(h1,u,v,w);
		addedge(h1,v,u,w);
	}
	fcnt=n;
	dis[1]=0;
	tarjan(1,-1);
	dep[1]=1;
	dfs(1,0);
//	pre();
//	for(int i=1;i<=cnt;i++){
//		printf("%d ",h2[i]);
//	}
//	printf("\n");
//	for(int i=1;i<=fcnt;i++){
//		printf("%d ",fval[i]);
//	}
//	printf("\n");
	while(q--){
		int u,v;
		read(u),read(v);
		int p=lca(u,v);
		if(p<=n){
			printf("%d\n",dis[u]+dis[v]-2*dis[p]);
		}
		else{
			int len=abs(sq[A]-sq[B]);
			int dAB=min(len,sc[A]-len);
			int d=dAB+dis[u]-dis[A]+dis[v]-dis[B];
			printf("%d\n",d);
		}
	}
	return 0;
}