题目描述

Alice 和 Bob 在玩一个游戏。

游戏在一棵有$n$个点的树上进行。最初，每个点上都只有一个数字，那个数字是$123456789123456789$。

有时，Alice 会选择一条从$s$到$t$的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点$r$，若$r$与$s$的距离是$\mathrm{dis}$，那么 Alice 在点$r$上添加的数字是$a \cdot \mathrm{dis} + b$。有时，Bob 会选择一条从$s$到$t$的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。

Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。

Bob 需要你帮他找出他能够选择的最小的数字。

输入格式

第一行两个数字$n$、$m$，表示树的点数和进行的操作数。
接下来$n-1$行，每行三个数字$u$、$v$、$w$，表示树上有一条连接$u$、$v$的边，长度是$w$。
接下来$m$行。每行第一个数字是$1$或$2$。
若第一个数是$1$，表示 Alice 进行操作，接下来四个数字$s$、$t$、$a$、$b$。
若第一个数是$2$，表示 Bob 进行操作，接下来两个数字$s$、$t$。

输出格式

每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字。

样例

输入

3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3

输出

123456789123456789
6
-106

数据范围与提示

• 测试点 1 ~ 2：$1 \le n \leq 10$，$1 \le m \leq 10$，$|a| \leq 10000$；
• 测试点 3 ~ 4：$1 \le n \leq 1000$，$1 \le m \leq 1000$，$|a| \leq 10000$；
• 测试点 5：$1 \le n \leq 100000$，$1 \le m \leq 100000$，$a = 0$，树是一条链；
• 测试点 6 ~ 7：$1 \le n \leq 100000$，$1 \le m \leq 100000$，$a = 0$；
• 测试点 8：$1 \le n \leq 100000$，$1 \le m \leq 100000$，$a = 1$，树是一条链；
• 测试点 9 ~ 10：$1 \le n \leq 100000$，$1 \le m \leq 100000$，$a = 1$；
• 测试点 11 ~ 13：$1 \le n \leq 100000$，$1 \le m \leq 100000$，$|a| \leq 10000$，树是一条链；
• 测试点 14 ~ 20：$1 \le n \leq 100000$，$1 \le m \leq 100000$，$|a| \leq 10000$，$1 \le u,v,s,t \le n$，$1 \le w \le 10^9$，$|b| \le 10^9$。