题目描述

旅游是很令人向往的，小毛驴也不例外。它想出去旅行，感受一下田园风光，便独自来到了一个风光秀美的湖边。对照湖边的导游图，小毛驴发现这个湖有N( 2 <= N <= 10000 )个岛屿，分别被标记为0…N-1。任何两个岛屿之间都没有陆路相通，为了保证任意两个岛屿之间都相互连通，旅游公司派了N-1条船，每条船往返于固定的两个岛之间。如果两个岛之间有船，那么最多只能有一条船。现在，小毛驴的难题是它想知道从一个岛屿去另外一个岛屿所需要的最少乘船时间，你能告诉他吗？

输入要求

输入的第一行是一个整数T( 1 <= T <= 100 )，表示有几组输入数据。
第一行是一个整数N，接下来的第2到第N行中每行3个整数：L R D。分别表示岛屿L(0 <= L < N)与岛屿R(0 <= R < N)之间的船开一次的时间D( 1 <= D <= 1000 )( 可以认为船来一次和去一次的时间是一样的 )。第N+1行是一个整数K ( 1 <= K <= 10000 )，接下来的第N+2到第N+2+K行每行两个整数：L R。表示一个问题：从L岛到R岛的最少乘船时间是多少？

输出要求

对应每个问题输出一个整数，表示两个岛屿之间的最少乘船时间。

输入样例

1
3
0 1 10
0 2 3
2
0 1
1 2

输出样例

10
13

提示

来源