题目描述

你是一处金矿的主人，并且有若干矿工要来这里挖黄金。

这处宝藏有 $n$ 个可能的藏宝点，这 $n$ 个点构成了一棵有根树的结构。

树上的每条边都是有向的，从父亲指向儿子，并且有个正整数权值 $c_i$，表示每有一个矿工从这条边走过，你会收取 $c_i$ 的过路费。

每个矿工 $x$ 会从某一个藏宝点 $u$ 出发，并且有一个正整数权值 $P_x$，表示如果你允许他来挖宝，将会获得 $P_x$ 的入场费。

某个藏宝点 $u$ 可能还会出现一块权值为 $Q_y$ 黄金，表示如果有矿工挖取了这个黄金，你会从中提走 $Q_y $的利润。

一个矿工 $x$ 挖取一块黄金 $y$ 的收益是 $P_x+Qy+\sum{e}{c_e}$，其中边 $e$ 在人 $x$ 和黄金 $y$ 的路径上。

注意一个矿工只能挖取一块黄金，一块黄金也只能被一个矿工挖取。一个矿工只能挖取他沿着树上有向边能到的黄金，同一条边在同一个挖取方案中可以被多个人经过。

一开始既没有黄金也没有矿工。

我们需要支持 $q$ 次操作，每次操作有两种类型：

• $1$ $u$ $v$：表示在点 $u$ 上新出现了一个权为 $v$ 的矿工。
• $2$ $u$ $v$：表示在点 $u$ 上新出现了一块权为 $v$ 的黄金。

你需要在每次操作后算出，如果让某些矿工去挖取黄金，那么可能的最大收益是多少。

注意你并不需要最大化挖到黄金的人数量。

输入格式

从标准输入读入数据。

第一行两个整数 $n$ 和 $q$，表示树的节点和操作数。

接下来 $n-1$ 行，每行三个正整数 $u,v,c$，表示有一条权为 $c$ 的边从点 $u$ 指向点 $v$。

接下来 $q$ 行每行描述一次操作。

输出格式

输出到标准输出。

对于每次操作，输出一个整数表示这次操作执行后的答案。

样例

input

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

output

0
6
6
6
17

第二次操作后，最优匹配方案是，让第一次操作添加的矿工挖去第二次操作添加的黄金。

第五次操作后，最优匹配方案为，在前一方案的基础上，让第四次操作添加的矿工挖去第五次操作添加的黄金。

见下发文件。

见下发文件。

数据范围与提示

对于所有数据，保证 $n,q \le 10^5$，并且所有树边的权均为不超过 $10^3$ 的正整数，所有矿工和黄金的权均为不超过 $10^8$ 的正整数。

表格中的特殊性质

• A：第 $i$ 条边从 $i$ 指向 $i+1$
• B：第 $i$ 条边从 $\lfloor \frac{i+1}{2} \rfloor$ 指向 $i+1$
• C：在树的形态上无特殊约束
• 1：保证所有 $1$ 操作都在 $2$ 操作之后
• 2：在操作类型上无特殊约束