Description

Alice and Bob are playing a game.

The game is played on a tree with $n$ vertices. Initially, each vertex contains exactly one number, which is $123456789123456789$.

Sometimes, Alice chooses the path from $s$ to $t$ and adds a number to every vertex on this path. For a vertex $r$ on the path, if the distance between $r$ and $s$ is $dis$, then the number Alice adds to $r$ is $a \times dis + b$.

Sometimes, Bob chooses the path from $s$ to $t$. He must first choose a vertex on this path, and then choose one number stored at that vertex.

Bob wants the chosen number to be as small as possible, but the large amount of numbers makes him dazzled. He needs your help to find the smallest number he can choose.

Input Format

The first line contains two integers $n, m$, the number of vertices of the tree and the number of operations.

The next $n - 1$ lines each contain three integers $u, v, w$, indicating there is an edge connecting $u$ and $v$ with length $w$.

The next $m$ lines each begin with an integer $1$ or $2$.

If the first integer is $1$, it denotes Alice’s operation, followed by four integers $s, t, a, b$.

If the first integer is $2$, it denotes Bob’s operation, followed by two integers $s, t$.

Output Format

Each time Bob performs an operation, output one line with a single integer, representing the smallest number he can choose.

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

Hint

Test points 1–2: $n \leq 10$, $m \leq 10$, $|a| \leq 10000$.

Test points 3–4: $n \leq 1000$, $m \leq 1000$, $|a| \leq 10000$.

Test point 5: $n \leq 100000$, $m \leq 100000$, $a = 0$, the tree is a path.

Test points 6–7: $n \leq 100000$, $m \leq 100000$, $a = 0$.

Test point 8: $n \leq 100000$, $m \leq 100000$, $a = 1$, the tree is a path.

Test points 9–10: $n \leq 100000$, $m \leq 100000$, $a = 1$.

Test points 11–13: $n \leq 100000$, $m \leq 100000$, $|a| \leq 10000$, the tree is a path.

Test points 14–20: $n \leq 100000$, $m \leq 100000$, $|a| \leq 10000$.

For all testdata, $0 \le w, |b| \le 10^9$.

Translated by ChatGPT 5