题目描述

在一个村庄里有 $n$ 座房子，这些房子通过一些双向道路连接。每天人们总是喜欢问这样的问题：“如果我想从房子 A 到房子 B，距离有多远？” 通常很难回答。但幸运的是，在这个村庄里，答案总是唯一的，因为道路的建造方式使得每两座房子之间都有一条唯一的简单路径（“简单” 意味着你不能两次经过同一个地方）。

你的任务是回答所有这些好奇的人。

输入格式

第一行是一个整数 $T\ (T \le 10)$，表示测试用例的数量。

对于每个测试用例：

第一行有两个数字 $n\ (2 \le n \le 40000)$ 和 $m\ (1\le m \le 200)$，分别表示房子的数量和查询的数量。

接下来的 $n-1$ 行，每行包含三个数字 $i$、$j$、$k$，用空格分隔，表示有一条连接房子 i 和房子 j 的道路，长度为 $k\ (1 \le k\le 40000)$。房子的编号从 $1$ 到 $n$。

接下来的 $m$ 行，每行有两个不同的整数 $i$ 和 $j$，你需要回答房子 i 和房子 j 之间的距离。

输出格式

对于每个测试用例，输出 $m$ 行。每行表示一个查询的答案。

样例

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