题目背景

薄荷小镇把所有路口都竖了路牌，任意两个路口之间最多只有一条小路相连。每条小路都很短：要么算 1 段路，要么算 2 段路。 你是「步行志愿者」的路线规划师。一次出行你会带一个「体力包」，每一步最多能支撑你走 c 段路（可以少走，不能超过）。你只能在路口休息、补水，然后再继续走——不能停在半路上。

现在有很多次出行计划，每次从路口 u 出发到路口 v。请你告诉大家：在“每一步最多走 c 段路，且必须在路口停下”的规则下，从 u 到 v 至少需要几步。

说明：两点之间的“距离”定义为它们之间那条唯一小路的段数和（每条小路的段数是 1 或 2）。

题目描述

给定一棵有 $n$ 个路口的小镇路网（是一棵树），每条边的段数 $z\in\{1,2\}$。接着给出 $m$ 次出行计划。对第 $i$ 次计划，给出 $(u,v,c)$：每一步最多可走 $c$ 段路，问从 $u$ 走到 $v$ 至少需要多少步。 你可以把路径想象成“从 $u$ 一直走到与 $v$ 的第一处公共分叉（最近公共路口），再从那儿走向 $v$”。每一步必须以一个路口为终点；如果两边最后各剩下一小段，有时可以把这两小段合成同一步完成。

输入格式

1. 第一行一个整数 $n$ —— 路口数。
2. 接下来 $n-1$ 行，每行三个整数 $x,y,z$ —— 表示有一条小路连接路口 $x$ 与 $y$，其段数为 $z\in\{1,2\}$。
3. 下一行一个整数 $m$ —— 出行计划数。
4. 接下来 $m$ 行，每行三个整数 $u,v,c$ —— 表示一次出行计划。

输出格式

对每次出行计划，输出一行一个整数，表示最少需要的步数。

样例输入 1

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

样例输出 1

1
2
1
1
1

样例解释（口语化理解）： 比如计划 $(1,3,2)$：1 到 3 的距离是 $1+2=3$ 段路。每一步最多 2 段路，最少需要 2 步。 对于 $(1,5,3)$：1 到 5 的距离是 $2+1=3$，一步走完。

数据范围与约定

• 共 10 组数据。
• 测试点 1、2（20 分）：$n,m\le 1000$。
• 测试点 3、4（20 分）：输入保证路网是一条链。
• 全部数据（60 分）： $1\le n,m\le 50000$，$1\le x,y,u,v\le n$，$1\le z\le 2$，$2\le c\le 2n$。 输入保证给出的是一棵树。