1 //2328MS    3728K    2757 B    G++
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<math.h>
  5 #define N 20005
  6 struct node{
  7     int u,v,d;
  8     int next;
  9 }edge[2*N];
 10 int num,n,head[N];
 11 int root[2*N],rank[N];
 12 int dep[2*N],dis[N];
 13 int dp[2*N][30],vis[N];
 14 int set[N];
 15 void addedge(int u,int v,int d)
 16 {
 17     edge[num].u=u;
 18     edge[num].v=v;
 19     edge[num].d=d;
 20     edge[num].next=head[u];
 21     head[u]=num++;
 22 }
 23 int Min(int a,int b)
 24 {
 25     return dep[a]<dep[b]?a:b;
 26 }
 27 int find(int x)
 28 {
 29     if(set[x]!=x) 
 30         set[x]=find(set[x]);
 31     return set[x];
 32 }
 33 void merge(int a,int b)
 34 {
 35     int x=find(a);
 36     int y=find(b);
 37     if(x>y) set[x]=y;
 38     else set[y]=x;
 39 }
 40 void dfs(int u,int deep)
 41 {
 42     vis[u]=1;
 43     root[++num]=u;
 44     rank[u]=num;
 45     dep[num]=deep;
 46     for(int i=head[u];i!=-1;i=edge[i].next){
 47         int v=edge[i].v,d=edge[i].d;
 48         if(vis[v]) continue;
 49         dis[v]=dis[u]+d;
 50         dfs(v,deep+1);
 51         root[++num]=u;
 52         dep[num]=deep; 
 53     }
 54 }
 55 void init()
 56 {
 57     int nn=2*n-1;
 58     int m=(int)(log(nn*1.0)/log(2.0));
 59     for(int i=1;i<=nn;i++)
 60         dp[i][0]=i;
 61     for(int j=1;j<=m;j++)
 62         for(int i=1;i+(1<<j)-1<=nn;i++)
 63             dp[i][j]=Min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
 64 }
 65 int RMQ(int l,int r)
 66 {
 67     int m=(int)(log((r-l+1)*1.0)/log(2.0));
 68     return Min(dp[l][m],dp[r-(1<<m)+1][m]);
 69 }
 70 int LCA(int u,int v)
 71 {
 72     int a=rank[u];
 73     int b=rank[v];
 74     if(a>b) return root[RMQ(b,a)];
 75     else return root[RMQ(a,b)];
 76 }
 77 int main(void) 
 78 {
 79     int m,c,u,v,d;
 80     int in[N];
 81     while(scanf("%d%d%d",&n,&m,&c)!=EOF)
 82     {
 83         memset(edge,0,sizeof(edge));
 84         memset(vis,0,sizeof(vis));
 85         memset(head,-1,sizeof(head));
 86         memset(in,0,sizeof(in));
 87         for(int i=0;i<=n;i++) set[i]=i;
 88         num=0;
 89         for(int i=0;i<m;i++){
 90             scanf("%d%d%d",&u,&v,&d);
 91             addedge(u,v,d);
 92             addedge(v,u,d);
 93             in[v]++;
 94             merge(u,v);
 95         }
 96         for(int i=1;i<=n;i++) //连接森林的所有树 
 97             if(in[i]==0){
 98                 addedge(0,i,0);
 99                 addedge(i,0,0);
100             }
101         num=0;
102         dis[0]=0;
103         dfs(0,1);
104         init();
105         //for(int i=1;i<=2*n-1;i++) printf(i==2*n-1?"%d\n":"%d ",root[i]); 
106         //for(int i=1;i<=2*n-1;i++) printf(i==2*n-1?"%d\n":"%d ",dep[i]);
107         //for(int i=1;i<=2*n-1;i++) printf(i==2*n-1?"%d\n":"%d ",dis[i]);
108         //for(int i=1;i<=2*n-1;i++) printf(i==2*n-1?"%d\n":"%d ",rank[i]);
109         while(c--){
110             scanf("%d%d",&u,&v);
111             //printf("*%d %d\n",find(u),find(v));
112             if(find(u)!=find(v)) puts("Not connected");
113             else printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
114         }
115     }
116     return 0;
117 }