CF1023G.Pisces

A group of researchers are studying fish population in a natural system of lakes and rivers. The system contains $n$ lakes connected by $n - 1$ rivers. Each river has integer length (in kilometers) and can be traversed in both directions. It is possible to travel between any pair of lakes by traversing the rivers (that is, the network of lakes and rivers form a tree).

There is an unknown number of indistinguishable fish living in the lakes. On day $1$, fish can be at arbitrary lakes. Fish can travel between lakes by swimming the rivers. Each fish can swim a river $l$ kilometers long in any direction in $l$ days. Further, each fish can stay any number of days in any particular lake it visits. No fish ever appear or disappear from the lake system. Each lake can accomodate any number of fish at any time.

The researchers made several observations. The $j$-th of these observations is "on day $d_j$ there were at least $f_j$ distinct fish in the lake $p_j$". Help the researchers in determining the smallest possible total number of fish living in the lake system that doesn't contradict the observations.

一群研究人员正在研究一个天然湖泊与河流系统中的鱼类种群。该系统包含 $n$ 个湖泊，由 $n - 1$ 条河流连接。每条河流具有整数长度（单位：千米），且可双向通行。任意两个湖泊之间均可通过河流相互到达（即湖泊与河流构成一棵树）。

湖泊中生活着未知数量的、彼此不可区分的鱼。第 $1$ 天时，鱼可以位于任意湖泊中。鱼可通过在河流中游泳在湖泊间移动：一条长度为 $l$ 千米的河流，鱼可在 $l$ 天内沿任意方向游过。此外，每条鱼可在其访问的任一湖泊中停留任意天数。在整个湖泊系统中，既无新鱼出现，也无鱼消失。每个湖泊在任意时刻均可容纳任意数量的鱼。

研究人员进行了若干次观测。第 $j$ 次观测的内容为：“在第 $d_j$ 天，湖泊 $p_j$ 中至少有 $f_j$ 条不同的鱼。” 请帮助研究人员确定不与这些观测相矛盾的、湖泊系统中鱼的最小可能总数。

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$) — the number of lakes in the system.

The next $n - 1$ lines describe the rivers. The $i$-th of these lines contains three integers $u_i$, $v_i$, $l_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$, $1 \leq l_i \leq 10^3$) — $1$-based indices of lakes connected by the $i$-th river, and the length of this river.

The next line contains a single integer $k$ ($1 \leq k \leq 10^5$) — the number of observations.

The next $k$ lines describe the observations. The $j$-th of these lines contains three integers $d_j$, $f_j$, $p_j$ ($1 \leq d_j \leq 10^8$, $1 \leq f_j \leq 10^4$, $1 \leq p_j \leq n$) — the day, the number of fish, and the lake index of the $j$-th observation. No two observations happen on the same day at the same lake simultaneously.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 系统中湖泊的数量。

接下来的 $n - 1$ 行描述河流。其中第 $i$ 行包含三个整数 $u_i$、$v_i$、$l_i$（$1 \leq u_i, v_i \leq n$，$u_i \neq v_i$，$1 \leq l_i \leq 10^3$）—— 分别表示由第 $i$ 条河流连接的两个湖泊的编号（从 1 开始计数）以及该河流的长度。

下一行包含一个整数 $k$（$1 \leq k \leq 10^5$）—— 观测次数。

接下来的 $k$ 行描述各次观测。其中第 $j$ 行包含三个整数 $d_j$、$f_j$、$p_j$（$1 \leq d_j \leq 10^8$，$1 \leq f_j \leq 10^4$，$1 \leq p_j \leq n$）—— 分别表示第 $j$ 次观测发生的日期、鱼的数量以及观测所在的湖泊编号。任意两次观测不会在同一天、同一湖泊同时发生。

Print one integer — the smallest total number of fish not contradicting the observations.

输出一个整数——与所有观测结果都不矛盾的鱼的最小总数。

In the first example, there could be one fish swimming through lakes $2$, $1$, and $4$, and the second fish swimming through lakes $3$, $1$, and $2$.

In the second example a single fish can not possibly be part of all observations simultaneously, but two fish swimming $2 \to 1 \to 4$ and $3 \to 1 \to 5$ can.

In the third example one fish can move from lake $1$ to lake $5$, others staying in their lakes during all time: two fish in lake $4$, six fish in lake $5$, one fish in lake $3$. The system of lakes is shown on the picture.

在第一个例子中，可能存在一条鱼依次游过湖泊 $2$、$1$ 和 $4$，另一条鱼依次游过湖泊 $3$、$1$ 和 $2$。

在第二个例子中，单条鱼不可能同时满足所有观测结果，但两条鱼分别按 $2 \to 1 \to 4$ 和 $3 \to 1 \to 5$ 的路径游动则可以满足。

在第三个例子中，一条鱼可以从湖泊 $1$ 移动到湖泊 $5$，其余鱼在整个时间段内始终停留在各自的湖泊中：湖泊 $4$ 中有两条鱼，湖泊 $5$ 中有六条鱼，湖泊 $3$ 中有一条鱼。湖泊系统的结构如图所示。