Gặp gỡ

Đất nước \(Z\) có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) . Có đúng \(n - 1\) con đường hai chiều nối giữa các thành phố thỏa mãn điều kiện: có thể đi từ thành phố bất kì đến tất cả các thành phố còn lại theo đường trực tiếp hoặc gián tiếp qua các thành phố khác. Đất nước \(Z\) thường có các
sự kiện văn hóa lớn, mỗi lần sự kiện sẽ được tổ chức tại một thành phố, điều này ảnh hưởng tới chi phí di chuyển trên các con đường. Cụ thể, nếu thành phố \(u\) là thành phố tổ chức sự kiện văn hóa, khi đó các con đường hướng tới thành phố \(u\) sẽ có chi phí là \(a\) còn các con đường đi xa thành phố \(u\) sẽ có chi phí là \(b\). Con đường từ \(i\) tới \(j\) được gọi là hướng tới \(u\) nếu đường đi ngắn nhất từ \(i\) tới \(u\) dài hơn đường đi ngắn nhất \(j\) từ tới \(u\), ngược lại thì con đường từ \(i\) tới \(j\) được gọi là đi xa thành phố \(u\) . Khi sự kiện văn hóa diễn ra, một người di chuyển qua \(s\) con đường sẽ bị mất chi phí bằng tổng của từng lần di chuyển, lần di chuyển thứ \(k\) \((1 \leq k \leq s)\), sẽ mất chi phí \(k \cdot cost_{k}\) , trong đó \(cost_{k}\) bằng \(a\) hoặc \(b\) tùy thuộc lần di chuyển thứ đi qua con đường hướng tới thành phố tổ chức sự kiện
hay đi xa thành phố tổ chức sự kiện.

Một câu hỏi thường gặp ở đất nước \(Z\) là: nếu sự kiện văn hóa diễn tại thành phố \(u\), có hai người ở thành phố \(i\) và thành phố \(j\) thì chi phí nhỏ nhất để hai người gặp nhau tại một thành phố nào đó là bao nhiêu.

Yêu cầu: Cho thông tin về các con đường của đất nước \(Z\) và \(q\) câu hỏi, mỗi câu hỏi được mô tả bằng \(5\) số \(u, i, j, a, b\) cần trả lời chi phí nhỏ nhất để hai người gặp nhau.

Input

Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\);

\(n - 1\) dòng sau, mỗi dòng chứa hai số nguyên \(x, y\) mô tả con đường nối giữa hai thành phố \(x, y\);

\(q\) dòng sau, mỗi dòng chứa năm số nguyên dương \(u, i, j, a, b\) mô tả một câu hỏi.

Output

Gồm \(q\) dòng, mỗi dòng là trả lời của câu hỏi trong
dữ liệu vào.

Example

8 3
1 2
5 6
5 3
4 3
8 2
3 1
7 5
3 3 2 5 2
5 8 7 8 12
1 4 7 10 2

6
80
20

Scoring

Có \(30\%\) số test tương ứng với \(30\%\) số điểm có : \(n, q \leq 1000\).

Có \(30\%\) số test tương ứng với \(30\%\) số điểm có : \(n \leq 2000\) và \(q \leq 10^5\).

Có \(20\%\) số test tương ứng với \(20\%\) số điểm có : \(n, q \leq 10^5\) và \(b \geq n \cdot a\).

Có \(20\%\) số test tương ứng với \(20\%\) số điểm có : \(n, q \leq 10^5\).