Bài 5. Gặp gỡ (7 điểm)

Đấ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 từ \(j\) 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 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 \le k \le s\)) sẽ mất chi phí \(k \cdot \text{cost}_k\), trong đó \(\text{cost}_k\) bằng \(a\) hoặc \(b\) tùy thuộc lần di chuyển thứ \(k\) đ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 mô tả con đường nối giữa hai thành phố;
• \(q\) dòng sau, mỗi dòng chứa năm số nguyên dương mô tả một câu hỏi.

Output

• Ghi ra file văn bản MEETING.OUT 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 ứng với \(30\%\) số điểm của bài thỏa mãn: \(n, q \le 2000\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm của bài thỏa mãn: \(n, q \le 50000\) và các câu hỏi có \(u = 1\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm của bài thỏa mãn: \(n, q \le 50000\) và các câu hỏi có \(a = b\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thỏa mãn: \(n, q \le 50000\).