问题描述

给定一棵树，树上有 $n$ 个结点（编号 $1 \ldots n$）和 $n-1$ 条无向边，每条边都有一个权值。

给定 $m$ 个询问，每个询问包含两个整数 $u$ 和 $v$，表示树上两点的距离。

输入格式

第一行包含一个整数 $n,m$，表示树的结点数与查询数。

接下来 $n-1$ 行，每行包含三个整数 $u,v,w$，表示点 $u$ 和点 $v$ 之间的边的权值为 $w$。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示查询点 $u$ 到点 $v$ 的距离。

$(2\le n,m\le 10^5,1\le u,v\le n,1\le w\le 100)$

输出格式

对于每个询问，输出一行一个整数，表示两点之间的距离。

样例输入

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

样例输出

10
25