题目描述
勇气小镇是一个有着n个房屋的小镇，为什么把它叫做勇气小镇呢，这个故事就要从勇气小镇成立的那天说起了，修建小镇的时候，为了让小镇有特色，镇长特地只修了n-1条路，并且规定说，所有在勇气小镇的村民，每一次出门必须规划好路线, 路线必须满足在到达终点之前绝对不走回头路。每个人都要这样，不然那个人就不配在小镇生活下去，因为他没有这个勇气。
事实上，这并不能算一项挑战，因为n-1条路已经连通了每户人家，不回头地从起点到终点，只是一个时间上的问题。
由于小镇上的福利特别好，所以小懒入住了这个小镇，他规划了m次的行程，每次从L房屋到R房屋,他想问你他每次从L房屋到R房屋需要走多远的路。
输入
输入的第一行是一个整数t，表示有t组数据
每组数据第一行是n,m两个数字，分别表示小镇上房屋的个数，和小懒计划的行程的数量。
之后第2行到第n行，每行三个整数a,b,c表示，a房屋与b房屋之间连接着一条距离为c的小路。
第n+1行到第n+m行，每行两个整数，L,R，代表一次小懒的询问，也就是询问小懒从L房屋走到R房屋所走的最近距离为多少。
输出
对于每组测试数据输出m行，每行一个整数，代表小懒从询问的L到R需要走的最近的距离
2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1
提示
【数据范围】
t<=10
2<=n<=40000
1<=m<=200
1<=a<=n
1<=b<=n
1<=c<=40000
1<=L<=n
1<=R<=n