A101179.村庄问路

村庄里有 $n$ 座房子，并且有一些双向道路连接它们。每天人们总爱问这样的问题：

“如果我想从房子 $A$ 去到房子 $B$，距离是多少？”

通常这个问题并不容易快速回答。但幸运的是，这个村庄的道路修建方式非常特殊：任意两座房子之间都存在且仅存在一条简单路径（简单路径指路径上不会重复经过同一个房子）。

你的任务是回答所有人的询问，即求出每次询问中从房子 $A$ 到房子 $B$ 的最短路长度（由于路径唯一，因此答案唯一）。

第一行是一个整数 $T$（$T \le 10$），表示测试数据组数。

对于每组测试数据：

• 第一行包含两个整数 $n$ 和 $m$
  其中 $2 \le n \le 40000$，$1 \le m \le 200$
  分别表示房子的数量和询问的数量。

• 接下来 $n-1$ 行，每行包含三个整数 $i, j, k$，表示有一条长度为 $k$ 的双向道路连接房子 $i$ 和房子 $j$。
  其中 $1 \le i,j \le n$，$0 < k \le 40000$。

• 接下来 $m$ 行，每行包含两个互不相同的整数 $i, j$，表示一次询问：求房子 $i$ 到房子 $j$ 的距离。

对于每组测试数据，输出 $m$ 行，每行输出对应询问的答案。

每组测试数据输出完毕后，额外输出一个空行。