你是一处金矿的主人，并且有若干矿工要来这里挖黄金。
这处宝藏有 个可能的藏宝点，这 个点构成了一棵有根树的结构。
树上的每条边都是有向的，从父亲指向儿子，并且有个正整数权值 ，表示每有一个矿工从这条边走过，你会收取 的过路费。
每个矿工 会从某一个藏宝点 出发，并且有一个正整数权值 ，表示如果你允许他来挖宝，将会获得 的入场费。
某个藏宝点 可能还会出现一块权值为 黄金，表示如果有矿工挖取了这个黄金，你会从中提走 的利润。
一个矿工 挖取一块黄金 的收益是 ，其中边 在人 和黄金 的路径上。
注意一个矿工只能挖取一块黄金，一块黄金也只能被一个矿工挖取。一个矿工只能挖取他沿着树上有向边能到的黄金，同一条边在同一个挖取方案中可以被多个人经过。
一开始既没有黄金也没有矿工。
我们需要支持 次操作，每次操作有两种类型：
你需要在每次操作后算出，如果让某些矿工去挖取黄金，那么可能的最大收益是多少。
注意你并不需要最大化挖到黄金的人数量。
从标准输入读入数据。
第一行两个整数 和 ，表示树的节点和操作数。
接下来 行，每行三个正整数 ，表示有一条权为 的边从点 指向点 。
接下来 行每行描述一次操作。
输出到标准输出。
对于每次操作，输出一个整数表示这次操作执行后的答案。
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
0
6
6
6
17
第二次操作后，最优匹配方案是，让第一次操作添加的矿工挖去第二次操作添加的黄金。
第五次操作后，最优匹配方案为，在前一方案的基础上，让第四次操作添加的矿工挖去第五次操作添加的黄金。
见下发文件。
见下发文件。
对于所有数据，保证 ，并且所有树边的权均为不超过 的正整数，所有矿工和黄金的权均为不超过 的正整数。
| 测试点 | 特殊性质 | ||
|---|---|---|---|
| 1 | C2 | ||
| 2 | |||
| 3,4 | |||
| 5 ~ 10 | C1 | ||
| 11 ~ 13 | C2 | ||
| 14,15 | A1 | ||
| 16,17 | B1 | ||
| 18,19 | C1 | ||
| 20 ~ 24 | C2 | ||
| 25 | |||