最小路

Problem Description

一个n个点m条边的无向图，任意两点之间至少存在一条路径。定义一条路径的价值为这条路径中经过的边长度的最大值。每条路径中每条边可以经过多次。有q次查询,每次查询输入u,v,你需要输出u到v的所有路径中的价值最小的那条路径的价值。

 

Input

第一行一个正整数T，表示数据组数。(T<=5)
每一组第一行输入n,m,q,分别表示节点数,边数,查询数。(n<=100,100,m<=200,000,q<=100,000)
接下来一共m行,每行三个整数u,v,w。表示从u,v之间存在一条长度为w边。
接下来一共q行,每行两个整数u,v,输出u到v的所有路径中的价值最小的那条路径的价值(u!=v)。

 

Output

对于每一个查询输出一个价值。

 

Sample Input

 

Sample Output