坐标
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

我们给定两棵带权树 与 ，大小均为 ，定义点 的距离为 ；

即两者在树 上的距离加上两者在树 上的深度（我们认为树 的根为 ，同时深度定义为此点到根节点的路径的边权和）。你需要找到两个点并最大化两者间距离，支持修改树 上的边权。注意每次修改的点和都是随机生成的。

注意，你找到的两个点  应满足  

ps：我们保证树 T2 的生成方式为，对于所有点 i >= 2，其父亲为 [1, i-1] 中随机的一个点。

输入描述:

第一行三个正整数 ，其中  表示树 T_1 与 T_2 的大小， 表示变换次数。
接下来  行描述树 ，其中每行三个正整数  表示一条  的无向边，其边权为 
接下来  行描述树 ，其中每行三个正整数  表示一条  的无向边，其边权为 
接下来  行，每行两个正整数  ，表示树  中  到  的父亲的边的边权增大了 ，请注意树  的根为 ，保证

输出描述:

共  行，第一行一个正整数表示树  没有变换时的答案。

接下来  行每行一个正整数第  次变换后的答案。
示例1

输入

复制 
3 0
1 2 1
2 3 4
1 2 1
2 3 4

输出

复制 
10
示例2

输入

复制 
10 5
2 1 9169934
3 2 9139781
4 3 8204914
5 4 4022253
6 5 4461495
7 6 5451751
8 7 9161101
9 8 9325703
10 9 1755549
2 1 428512
3 2 3226094
4 3 4200469
5 3 7814858
6 4 8688657
7 2 5533607
8 5 1461632
9 5 9970292
10 5 8700469
10 183804036
6 238058020
3 576677263
5 898699625
7 522470322

输出

复制 
80862414
264666450
484269825
1637624351
3196352808
3196352808

备注:

，输入数据保证树  以及每次修改的端点随机生成。保证 ，保证 ，且 k > 0，保证