xcy orz

//仙人掌图用在线圆方树,具体题解可见洛谷NaCly_Fish的解释,本题解仅提供注意点
#include<bits/stdc++.h>
using namespace std;
const int M=40005;//由于会新增边,空间开得稍大
int n,m,tes;
int H1[M],T1[M],N1[M],v1[M],tot1;//存原边
int H[M],T[M],N[M],v[M],tot;//存建树后的边
int dfn[M],low[M],tim,ext;//前三个变量参考tarjan求割边,ext即包括方点和圆点的总和
int fa[M],len[M],s[M];
int f[M][16],dis[M],dep[M],A,B;
int read(){
    int res=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch))res=res*10+ch-'0',ch=getchar();
    return res;
}
void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+48);
}
void add1(int x,int y,int z){
    N1[++tot1]=H1[x],T1[tot1]=y,v1[tot1]=z,H1[x]=tot1;
}
void add(int x,int y,int z){
    N[++tot]=H[x],T[tot]=y,v[tot]=z,H[x]=tot;
}
void work(int x,int y,int v){//x是一个参照点假设为环的起点
    ++ext;//增加方点
    int now=y,sum=v;
    while(now!=fa[x]){
        s[now]=sum;
        sum+=len[now];
        now=fa[now];
    }//记录环上距离
    s[ext]=s[x],s[x]=0;
    now=y;
    while(now!=fa[x]){
        add(now,ext,min(s[now],s[ext]-s[now]));//取到x的最短距离作为到方点的边权
        add(ext,now,min(s[now],s[ext]-s[now]));
        now=fa[now];
    }
}
void tarjan(int x,int pre){//找环/建树(参考tarjan求割边)
    dfn[x]=low[x]=++tim;
    for(int i=H1[x];i;i=N1[i]){
        int y=T1[i];
        if(y==pre)continue;
        if(!dfn[y]){
            fa[y]=x;len[y]=v1[i];//len记录到父节点的距离
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
        }
        else low[x]=min(low[x],dfn[y]);
        if(low[y]>low[x])add(x,y,v1[i]),add(y,x,v1[i]);//是圆点间的边直接保留
    }
    for(int i=H1[x];i;i=N1[i]){
        int y=T1[i];
        if(fa[y]!=x&&dfn[y]>dfn[x])work(x,y,v1[i]);//判定非树边,注意不要忘记后一条件(若x比y后访问,fa[y]绝对不会是x)
    }
}
void dfs(int x,int pre,int DIS,int DEP){
    f[x][0]=pre;dis[x]=DIS;dep[x]=DEP;
    for(int i=H[x];i;i=N[i]){
        int y=T[i];
        if(y==pre)continue;
        dfs(y,x,DIS+v[i],DEP+1);
    }
}
void prework(){
    for(int k=1;k<=15;k++)
    for(int i=1;i<=ext;i++)
        f[i][k]=f[f[i][k-1]][k-1];
}
int LCA(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int k=15;k>=0;k--)if(dep[f[x][k]]>=dep[y])x=f[x][k];
    if(x==y)return x;//一定不是方点
    for(int k=15;k>=0;k--)if(f[x][k]!=f[y][k])x=f[x][k],y=f[y][k];
    A=x,B=y;//如果是方点,记录该方点在x,y方向的子节点
    return f[x][0];
}
int main()
{
    n=read(),m=read(),tes=read();
    ext=n;//原本已经有n个圆点
    for(int i=1,x,y,z;i<=m;i++){
        x=read(),y=read(),z=read();
        add1(x,y,z);add1(y,x,z);
    }
    tarjan(1,0);
    dfs(1,0,0,1);
    prework();
    while(tes--){
        int x=read(),y=read(),ans;
        int lca=LCA(x,y);
        if(lca<=n)ans=dis[x]+dis[y]-dis[lca]*2;//都是圆点直接做
        else{
            ans=dis[x]+dis[y]-dis[A]-dis[B];//先加上x->A和y->B的距离
            if(s[A]<s[B])swap(A,B);//防止小减大变负
            ans+=min(s[A]-s[B],s[lca]-(s[A]-s[B]));//取环上最短路
        }
        //根据仙人掌图性质不可能都是方点
        write(ans),puts("");
    }
}