题目背景

夏の終わりを知って$\\$ ラムネの雫に映る僕達は$\\$ 見失いそうな$\\$ 茜色の頬を追いかけて$\\$ 来年もまた此処に来るんだ

—— 夏が終わる - Nanatsukaze

一年时间，走一个环，再次回到原点。

在这个世界不间断的变化中，还有机会再遇到你吗？选择一条最优的路径时，又有多大的机会呢？

题目描述

给定一棵 $n$ 个点的树 $T$，边带权。定义无向完全图 $G(T)$：

• 包含 $n$ 个点。
• 如果 $T$ 中包含边 $u,v$，则 $G$ 上 $u,v$ 边的权值为这条边的权值；否则为 $0$。

记 $w(T)$ 为 $G(T)$ 的权值最小的哈密顿回路的权值。

给定 $q$ 次修改操作，分为两种：

• 在 $T$ 上删去一条边再加上一条边，保证每次操作后仍然是一棵树；
• 给定 $T$ 上的一条路径，给路径上的每一条边的边权增加一个值。

你需要在每次操作之后计算 $w(T)$。

输入格式

第一行两个正整数 $n,q$。

接下来 $n-1$ 行每行三个正整数 $u,v,w$ 表示树上的一条边，边按照输入顺序编号为 $1\sim n-1$。

接下来 $q$ 行每行 $4$ 或 $5$ 个整数，第一个整数表示操作编号 $opt$：

• 如果 $opt=1$，则表示删边再加边操作，接下来 $4$ 个整数依次为 $i,u,v,w$：$i$ 表示这一次操作删去的边的编号；$u,v,w$ 表示新加的边。这些新增的边按照操作顺序从 $n$ 开始依次向上编号。
• 如果 $opt=2$，则表示路径加操作，接下来 $3$ 个整数 $u,v,w$：表示给树上 $u,v$ 之间的简单路径上的每一条边的边权增加 $w$。

输出格式

$q$ 行每行一个整数表示操作后的 $w(T)$。

5 3
1 2 1
2 3 1
3 4 1
4 5 1
1 4 3 5 1
2 1 5 1
1 1 1 3 100

1
1
3

6 12
3 5 18
3 1 8
5 6 3
6 4 10
6 2 8
1 4 3 4 10
1 5 6 2 5
2 2 5 1
1 7 3 2 19
2 4 6 1
1 3 5 6 20
2 3 4 1
1 9 5 6 16
2 3 1 32
2 3 4 30
2 3 5 22
2 3 2 21

0
0
0
8
8
8
8
8
12
19
19
40

提示

【样例解释 #1】

第一次操作后，$G(T)$ 的形态如下：

其中树边用红色标出，最优的哈密顿回路之一为 $1-5-4-2-3-1$。

【数据范围】

对于所有数据，保证 $5\leq n\leq 1.5\times 10^5$，$1\leq q\leq 3\times 10^5$，$1\leq u,v\leq n$，$1\leq w\leq 2\times 10^{11}$，保证任意时刻边权不超过 $4\times 10^{11}$，保证不会重复删除已经删除的边。

捆绑测试，共 5 个 Subtask，具体限制如下所示：

• Subtask 1（6 pts）：$n\leq 10$，$q\leq 500$；
• Subtask 2（27 pts）：$n,q\leq 2000$；
• Subtask 3（15 pts）：所有答案均 $\geq 1$；
• Subtask 4（26 pts）：$n\leq 7.5\times 10^4$，$q\leq 1.5\times 10^5$；
• Subtask 5（26 pts）：无特殊限制。