You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给一颗 $n$ 个节点的无根树，边有边权，点从 $1$ 开始编号。令 $\text{dis}(x,y)$ 为点 $x$ 到点 $y$ 的距离。

你需要维护一个初始为空的点对集合 $S$。每次有两种操作：

• 1 a b 往 $S$ 中插入一个点对 $(a,b)$。
• 2 x y 查询下面式子的结果并输出：

若查询时 $S$ 为空，则输出 -1。

输入格式

第一行两个整数 $n,m$，分别表示树的点数以及操作次数。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，表示点 $u_i$ 与 $v_i$ 之间有一条长度为 $w_i$ 的边。

接下来 $m$ 行，每行三个整数，意义如题目所述。

输出格式

对于每个 2 x y，输出查询结果。

样例1

输入样例

5 10
3 4 19
4 5 18
2 5 14
1 2 19
2 5 4
1 2 5
2 4 5
1 1 5
2 1 3
2 3 4
1 1 3
2 2 3
1 2 1
2 2 1

输出样例

-1
32
37
69
19
0

数据范围

本题开启捆绑测试。

对于 $100\%$ 的数据，保证：$1\le n,m\le 2\times 10^5$，$1\le u_i,v_i,x,y\le n$，$1\le w_i\le 10^9$。

特殊性质 A：对于所有插入操作，满足 $b=1$。

特殊性质 B：$u_i=i,v_i=i+1$。

特殊性质 C：$u_i=1,v_i=i+1$。