题目描述

共有 $N$ 头奶牛（$2 \le N \le 1000$），编号为 $1 \sim N$，它们分别在编号同样为 $1 \sim N$ 的牧场上吃草，其中第 $i$ 头奶牛位于第 $i$ 号牧场。

牧场之间由 $N-1$ 条双向步道连接。第 $i$ 条步道连接牧场 $A_i$ 和 $B_i$，长度为 $L_i$（$1 \le L_i \le 10000$）。

任意两个不同牧场之间有且仅有一条通行路径，因此整张图构成一棵无根树。

现在给出 $Q$ 组询问，每组询问给定两个牧场编号 $p_1,p_2$，请你求出这两个牧场之间路径的总长度。

输入格式

• 第一行：两个整数 $N,Q$，分别表示牧场数量与询问组数。
• 第 $2 \sim N$ 行：每行三个整数 $A_i,B_i,L_i$，描述一条步道连接的两个牧场以及步道长度。
• 第 $N+1 \sim N+Q$ 行：每行两个整数 $p_1,p_2$，代表一组询问，查询对应两个牧场间的路径长度。

输出格式

• 共 $Q$ 行，每行输出一个整数，依次表示每组询问的答案，即两点之间路径的总长度。

4 2 
2 1 2 
4 3 2 
1 4 3 
1 2 
3 2 

2 
7 

提示

样例解释

• 第一组询问：牧场 $1$ 与牧场 $2$ 直接相连，路径长度为 $2$。
• 第二组询问：行走路径为 $3 \to 4 \to 1 \to 2$，总长度为 $2+3+2=7$。

数据范围

• $2 \le N \le 1000$
• $1 \le L_i \le 10000$
• $1 < Q < 1000$