Description

有$n$ 栋房屋，由一些双向道路连接起来。每两栋房屋之间都有一条独特的简单道路（“简单”意味着不可以通过两条道路去一个地方）。人们每天总是喜欢这样问：“我从A房屋到B房屋需要走多远？”

Format

Input

第1行是单个整数$T$ $（T ≤10）$，表示测试用例的数量。每个测试用例的第1行都包含$n （2≤n ≤40000）$和$m （1≤m ≤200）$，表示房屋数量和查询数量。下面的$n -1$行，每行都包含三个数字$i$、$j$、$k$，表示有一条道路连接房屋i和房屋j，长度为$k（0<k≤40000）$，房屋被标记为$1～n$ 。接下来的$m$ 行，每行都包含两个不同的整数$i$ 和$j$ ，求房屋$i$ 和房屋$j$之间的距离。

Output

对每个测试用例，都输出$m$ 行查询答案，在每个测试用例后都输出一个空行。

Samples

2
3 2
1 2 10
3 1 15
1 2
2 3
2 2
1 2 100
1 2
2 1

10
25

100
100