题目描述

给定一棵大小为 $n$ 的树，树上节点编号从 $1$ 到 $n$。树上有 $n-1$ 条边，第 $i$ 条边表示为三个整数 $u_i, v_i, w_i$，表示存在一条连接节点 $u_i$ 和 $v_i$ 的长度为 $w_i$ 的边。

有 $q$ 次询问，第 $i$ 次询问给定两个整数 $x_i$ 和 $y_i$，你需要回答出从节点 $x_i$ 出发到达节点 $y_i$ 的简单路径上最短的那条边的长度。

输入格式

第一行，一个整数 $n(1 \le n \le 10^5)$。

接下来 $n-1$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示树上的一条边（$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9$）。

接下来一行，一个整数 $q(1 \le q \le 10^5)$。

接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示一次询问（$1 \le x_i, y_i \le n, x_i \neq y_i$）。

输出格式

对于每次询问的 $x_i$ 和 $y_i$，输出一行，包含一个整数，表示以节点 $x_i$ 为起点，以节点 $y_i$ 为终点的简单路径上所有边的长度的最小值。

样例

6
1 2 1
2 3 2
2 4 3
4 5 4
4 6 5
3
1 5
2 4
3 6

1
3
2

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n, q \le 10; w_i \le 100$
• 对于 $60\%$ 的数据，$n, q \le 1000; w_i \le 10^5$
• 对于 $100\%$ 的数据，$1 \le n, q \le 10^5; 1 \le w_i \le 10^9$