Problem:
 Score : 600 points    Problem Statement There is a tree with N vertices numbered 1 to N .
The i -th edge in this tree connects Vertex a_i and Vertex b_i , and the color and length of that edge are c_i and d_i , respectively.
Here the color of each edge is represented by an integer between 1 and N-1 (inclusive). The same integer corresponds to the same color, and different integers correspond to different colors.  Answer the following Q queries:   Query j ( 1 \leq j \leq Q ): assuming that the length of every edge whose color is x_j is changed to y_j , find the distance between Vertex u_j and Vertex v_j . (The changes of the lengths of edges do not affect the subsequent queries.)       Constraints  2 \leq N \leq 10^5  1 \leq Q \leq 10^5  1 \leq a_i, b_i \leq N  1 \leq c_i \leq N-1  1 \leq d_i \leq 10^4  1 \leq x_j \leq N-1  1 \leq y_j \leq 10^4  1 \leq u_j < v_j \leq N  The given graph is a tree.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  Q  a_1  b_1  c_1  d_1  :  a_{N-1}  b_{N-1}  c_{N-1}  d_{N-1}  x_1  y_1  u_1  v_1  :  x_Q  y_Q  u_Q  v_Q       Output Print Q lines. The j -th line ( 1 \leq j \leq Q ) should contain the answer to Query j .        Sample Input 1 5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4      Sample Output 1 130
200
60  The graph in this input is as follows:   Here the edges of Color 1 are shown as solid red lines, the edge of Color 2 is shown as a bold green line, and the edge of Color 4 is shown as a blue dashed line.   Query 1 : Assuming that the length of every edge whose color is 1 is changed to 100 , the distance between Vertex 1 and Vertex 4 is 100 + 30 = 130 .  Query 2 : Assuming that the length of every edge whose color is 1 is changed to 100 , the distance between Vertex 1 and Vertex 5 is 100 + 100 = 200 .  Query 3 : Assuming that the length of every edge whose color is 3 is changed to 1000 (there is no such edge), the distance between Vertex 3 and Vertex 4 is 20 + 10 + 30 = 60 . Note that the edges of Color 1 now have their original lengths.

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 5 + 5)


def solve(n, links, queries):
    def _query(a, b, data, m0, INF):
        yield INF
        a += m0
        b += m0
        while a < b:
            if b & 1:
                b -= 1
                yield data[b - 1]
            if a & 1:
                yield data[a - 1]
                a += 1
            a >>= 1
            b >>= 1

    def query(u, v):
        fu = first_appear[u]
        fv = first_appear[v]
        if fu > fv:
            fu, fv = fv, fu
        return euler_tour[min(_query(fu, fv + 1, data, m0, INF))[1]]

    def dfs(v, p, dep):
        first_appear[v] = len(euler_tour)
        depth[v] = dep
        euler_tour.append(v)
        for u, _, _ in links[v]:
            if u == p:
                continue
            dfs(u, v, dep + 1)
            euler_tour.append(v)

    def dfs2(v, p, tmp_dists, total_dist):
        for x, arr in v_queries[v].items():
            arr[0] = total_dist - tmp_dists[x][0]
            arr[1] = tmp_dists[x][1]
        for u, uc, ud in links[v]:
            if u == p:
                continue
            tmp_dists[uc][0] += ud
            tmp_dists[uc][1] += 1
            dfs2(u, v, tmp_dists, total_dist + ud)
            tmp_dists[uc][0] -= ud
            tmp_dists[uc][1] -= 1

    
    INF = (n, None)

    
    euler_tour = []
    first_appear = [0] * n
    depth = [0] * n

    dfs(0, -1, 0)
    
    
    

    
    m = 2 * n
    m0 = 2 ** (m - 1).bit_length()
    data = [INF] * (2 * m0)
    for i, v in enumerate(euler_tour):
        data[m0 - 1 + i] = (depth[v], i)
    for i in range(m0 - 2, -1, -1):
        data[i] = min(data[2 * i + 1], data[2 * i + 2])

    

    v_queries = [{} for _ in range(n)]
    lca = []
    for i, (x, y, u, v) in enumerate(queries):
        w = query(u, v)
        lca.append(w)
        v_queries[u][x] = [0, 0]
        v_queries[v][x] = [0, 0]
        if w != 0:
            v_queries[w][x] = [0, 0]

    tmp_dists = defaultdict(lambda: [0, 0])
    dfs2(0, -1, tmp_dists, 0)

    ans = []
    for w, (x, y, u, v) in zip(lca, queries):
        qu = v_queries[u][x]
        qv = v_queries[v][x]
        du = qu[0] + qu[1] * y
        dv = qv[0] + qv[1] * y
        if w == 0:
            ans.append(du + dv)
            continue
        qw = v_queries[w][x]
        dw = qw[0] + qw[1] * y
        ans.append(du + dv - 2 * dw)

    return ans


n, q = list(map(int, input().split()))
links = [set() for _ in range(n)]
lines = sys.stdin.readlines()
for line in lines[:n - 1]:
    a, b, c, d = list(map(int, line.split()))
    a -= 1
    b -= 1
    links[a].add((b, c, d))
    links[b].add((a, c, d))
queries = []
for line in lines[n - 1:]:
    x, y, u, v = map(int, line.split())
    u -= 1
    v -= 1
    queries.append((x, y, u, v))

ans = solve(n, links, queries)

print('\n'.join(map(str, ans)))