图不一定联通，所以用并查集找各个联通块的祖先分别建图，之后就和LCA的步骤差不多了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
inline int read(){
int sum=0,x=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
x=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
return x?sum:-sum;;
}
inline void write(int x){
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
}
const int M=1e4+4;
const int maxlog=14;
struct node{
int v,nextt,w;
}e[M<<2];
int head[M],deep[M],grand[M][maxlog],dis[M][maxlog],f[M],s,n,tot,root,sign;
void addedge(int u,int v,int w){
e[tot].v=v;
e[tot].w=w;
e[tot].nextt=head[u];
head[u]=tot++;
}
int find(int x){
return x==f[x]?x:f[x]=find(f[x]);
}
void dfs(int x){
for(int i=1;i<=s;i++){
grand[x][i]=grand[grand[x][i-1]][i-1];
dis[x][i]=dis[x][i-1]+dis[grand[x][i-1]][i-1];
if(!grand[x][i])
break;
}
for(int i=head[x];~i;i=e[i].nextt){
int v=e[i].v;
// cout<<"exit"<<endl;
if(v!=grand[x][0]){
grand[v][0]=x;
deep[v]=deep[x]+1;
dis[v][0]=e[i].w;
dfs(v);
}
}
}
void init(){
s=floor(log(n+0.0)/log(2.0));
deep[0]=-1;
dfs(root);
}
int LCA(int a,int b){
if(deep[a]>deep[b])
swap(a,b);
int ans=0;
for(int i=s;i>=0;i--)
if(deep[a]<deep[b]&&deep[a]<=deep[grand[b][i]])
ans+=dis[b][i],b=grand[b][i];
for(int i=s;i>=0;i--)
if(grand[a][i]!=grand[b][i])
ans+=dis[a][i],a=grand[a][i],ans+=dis[b][i],b=grand[b][i];
if(a!=b)
ans+=dis[a][0],ans+=dis[b][0];
return ans;
}
int main(){
int m,k;
while(~scanf("%d%d%d",&n,&m,&k)){
for(int i=0;i<=n;i++)
f[i]=i,head[i]=-1,deep[i]=0;
memset(grand,0,sizeof(grand));
memset(dis,0,sizeof(dis));
tot=0;
while(m--){
int x=read(),y=read(),w=read();
addedge(x,y,w);
addedge(y,x,w);
int p=find(x);
int q=find(y);
if(p!=q)
f[q]=p;
}
for(int i=1;i<=n;i++){
if(f[i]==i){
root=i;
init();
}
// cout<<"!!!"<<f[i]<<endl;
}
/* for(int i=1;i<=n;i++)
cout<<deep[i]<<" ";
cout<<endl;*/
while(k--){
int u=read(),v=read();
int x=find(u);
int y=find(v);
if(x==y){
write(LCA(u,v));
putchar('
');
}
else
puts("Not connected");
}
}
return 0;
}