5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

Not connected
6

/*
HDOJ  2874 公共祖先问题 LCA 
不太懂。。。看别人的 
	从根结点开始形成一棵深搜树，在回溯到结点u的时候，u的子树已经遍历，
这时候才把u结点放入合并集合中，这样u结点和所有u的子树中的结点的最近公共祖先就是u了，

	u和还未遍历的所有u的兄弟结点及子树中的最近公共祖先就是u的父亲结点。以此类推。。
这样我们在对树深度遍历的时候就很自然的将树中的结点分成若干的集合，
两个集合中的所属不同集合的任意一对顶点的公共祖先都是相同的，
也就是说这两个集合的最近公共最先只有一个。对于每个集合而言可以用并查集来优化，
时间复杂度就大大降低了，为O(n + q)，n为总结点数，q为询问结点对数。 

另外Tarjan解法，是一个离线算法，就是说它必须将所有询问先记录下来，
再一次性的求出每个点对的最近公共祖先，只有这样才可以达到降低时间复杂度
*/

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

#define N 10001 
#define N1 1000001

struct edge{  
    int to,w;
	edge(int a=0,int b=0){
		to=a;w=b;
	}  
      
}; 

int pre[N],dis[N],n,ans[N1],vis[N],mark[N];  
//pre[i]并查集所用，记录前继结点  
//dis[i]记录个点到跟结点的距离  
//ans记录m个询问的答案  
//vis标记查询过了的点  
//mark记录已访问过的根节点。由于已遍历的树所有结点的find都是根节点，这样就能判断下是否在别的树里了

vector<edge> e[N];//记录树  
vector<edge> q[N];//记录所求最短距离的两点  

int find(int x){  
    if(pre[x]!=x)  
        return pre[x]=find(pre[x]);  
    return pre[x];  
} 

void tarjan(int u)
{  
    int i,x;  
	 
    for(i=0;i<q[u].size();i++)//u节点，u可能到达多个地方 
	{  
        x=q[u][i].to;//u->到达的另一点 
        //如果所求两点中的对应点已知，则必定在同一子树上，
		//由于并查集只记录所在子树。所以find(x)，就是最近公共祖先 
		//q[u][i].w，第几次的询问 
		if(vis[x]&&ans[q[u][i].w]==-1&&mark[find(x)]!=1) 
        {
			ans[q[u][i].w]=dis[u]+dis[x]-2*dis[find(x)];  
        } 
    } 
	 
    for(i=0;i<e[u].size();i++)//查找
	{  
        x=e[u][i].to;
		if(!vis[x])
		{  
            vis[x]=1;
			dis[x]=dis[u]+e[u][i].w;  
            tarjan(x);  
            pre[x]=u;  
        }  
    }  
}

int main()
{
	int a,b,c,i,n,m,k;  
	
	//freopen("test.txt","r",stdin);
   
	while(scanf("%d%d%d",&n,&m,&k)!=EOF)
	{
        for(i=1;i<=n;i++)//初始化 
		{
			e[i].clear();
			q[i].clear();
			pre[i]=i;
			vis[i]=mark[i]=0;
		} 
		
		memset(ans,-1,sizeof(ans));
		
		for(i=0;i<m;i++) 
		{  
            scanf("%d%d%d",&a,&b,&c);  
            e[a].push_back(edge(b,c));//a->b 距离c 
        	e[b].push_back(edge(a,c));
		} 
        	
		for(i=1;i<=k;i++)
		{  
            scanf("%d%d",&a,&b);  
            q[a].push_back(edge(b,i));//a->b dii个询问
			q[b].push_back(edge(a,i)); 
        } 
        
        for(i=1;i<=n;i++)
		{  
            if(!vis[i])
            {
            	vis[i]=1;
				dis[i]=0;
				tarjan(i);
				mark[i]=1;	
            }
        } 
        
        for(i=1;i<=k;i++)
			if(ans[i]!=-1)
				printf("%d\n",ans[i]);
			else
				printf("Not connected\n");   
	}
	return 0;
} 

/* 
    最近公共祖先lca 离线算法/Tarjan算法,用mark标记是否在同一组里。  
    方法举例说明：  
                1  
               / \  
              2   3  
             / \  
            4   5  
           /   /  
          7   8  
         /   
        9    
    查询(4,9)：到4时，由于vis[9]=0，所以继续；到9后，最近公共祖先就是pre[4]=4（回溯的时候记录父节点）;  
    查询(9,8):深度优先搜索，所以到8时才询问；要到8必须回溯到2，在进到8这个子树，所以以记录pre[9]=7;pre[7]=4;pre[4]=2;pre[2]=2;所以find(2)=2;  
    查询(8,3):跟上条相似，必须回溯1才能到3，而find(8)=1就是最近公共祖先；  
    我们可以发现，对于查询的两点，都要在先查询到的点开始，回溯到最近公共祖先，才查询相对应的点 
*/