T284389 「ZHYOI-1」公路翻新

在一个城市里，存在着一些村子。某些村子之间有一条公路，这些公路都是双行道，而且都有一个美观度。这些村子的关系可以看成一颗树，但深度不会很深。如今，市政府觉得这些公路太古老了，决定对它们进行翻新。ZHY 作为这次任务的负责人，有时会接收到一些上级的命令或询问，请你帮他处理这些命令。

这个城市中一共有 $n$ 个村子，编号为 $1$ 到 $n$，默认根节点为 $1$ 号村子，**且深度不超过 $10^4$**。每个村子都有一个状态，要么是施工村，要么是停工村。初始每个村子都是施工村，中途某些村子可能会被设置为停工村。定义两个村子的距离是它们最短路径上会经过的村子数量，上级将会以 $3$ 种方式给 ZHY 下达命令： - `1 x v` 表示翻新命令，将 $x(1 \le x \le n)$ 号村子到距离它最近的停工村（包括它自己，如果有距离相同的就找编号最小的）的路径上的所有公路的美观值加上 $v(1 \le v \le 10^9)$，并输出这个距离它最近的停工村的编号。如果此时没有一个村子是停工村，输出 $-1$。 - `2 x y` 表示停工命令，将 $x(1 \le x \le n)$ 号村子到 $y(1 \le y \le n)$ 号村子的路径上的所有村子设置为停工村。**保证停工命令的数量不超过 $500$。** - `3 x` 表示询问命令，上级将询问以 $x(1 \le x \le n)$ 号村子为根的子树中的所有公路的美观值的最小值。如果 $x$ 号村子是叶子节点，输出 $-1$。

第一行一个正整数 $n$，表示村子的数量。 随后 $n-1$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u$ 号村子和 $v$ 号村子之间有一条美观度为 $w$ 的公路。**保证输入数据可以构成一颗根为 $1$ 的树，且树的深度不超过 $10^4$。** 随后一行一个正整数 $m$，表示命令和询问的总数量。 随后 $m$ 行，每行 $2$ 个或 $3$ 个整数表示一个命令或询问。**保证停工命令的数量不超过 $500$。**

对于每个翻新命令和询问命令，输出一行一个整数表示答案。

**本题采用捆绑测试。** | $\text{subtask}$ 编号 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $0$ | $n,m \le 7000$ | $5$ | | $1$ | 停工命令的数量以及树的深度不超过 $15$ | $20$ | | $2$ | 翻新命令与停工命令的数量总和不超过 $6000$ | $25$ | | $3$ | 无特殊限制 | $50$ | 对于 $100\%$ 的数据，$1 \le n,m \le 3 \times 10^5$，**保证树的深度不超过 $10^4$，且停工命令的数量不超过 $500$。**