题目描述

给定一个棵由编号为 $1$~$n$ 这 $n$ 个节点构成的树，树的第 $i$ 条边连接 $u_i,v_i$ ，边权为 $w_i$。

现在有 $q$ 组询问， 第 $i$ 组询问包含两个正整数 $x_i,y_i$，请你求出一个包含 $x_i,y_i$ 的连通块，并使得选中连通块的边权之和最大。

输入格式

输入第一行，两个正整数 $n,q$ 接下来 $n-1$ 行，每行三个正整数，分别表示每条边的 $u_i,v_i,w_i$ 接下来 $q$ 行，每行两个正整数，分别表示每组询问的 $x_i,y_i$

输出格式

输出共 $q$ 行，每行一个整数表示答案。

5 2
1 2 -10
2 3 3
2 4 5
1 5 2
2 5
3 4

0
8

数据范围

• 对于 $30\%$ 的数据，$1\leq n,q \leq 10$
• 对于 $60\%$ 的数据，$1\leq n,q \leq 10^3$
• 对于 $100\%$ 的数据，$1\leq n,q \leq 10^5$，$1 \leq u_i , v_i ,x_i,y_i \leq n$， $-10^9 \leq w_i \leq 10^9$