"Ngày xửa ngày xưa, có một Vùng đất Kỳ diệu được tạo ra bằng phép thuật của _minhduc..."

Tại Vùng đất Kỳ diệu — nơi tạo ra những cốc nước ép ngon nhất thế giới, có một mạng lưới gồm ~n~ thành phố chuyên dùng để pha chế nước ép. Các thành phố được đánh số từ ~1~ đến ~n~ và được kết nối với nhau bởi ~n - 1~ con đường hai chiều, đảm bảo luôn có thể đi từ bất kỳ thành phố nào đến thành phố khác.

Mỗi thành phố độc quyền sản xuất một loại nguyên liệu nước ép. Cụ thể, thành phố thứ ~i~ cung cấp loại nguyên liệu có độ ngon là ~d_i~, giá bán mỗi lít là ~p_i~ và trữ lượng tối đa là ~l_i~ lít.

Trong dịp lễ hội, có ~m~ đứa trẻ lần lượt đến tham quan vùng đất này. Các đứa trẻ được đánh số từ ~1~ đến ~m~. Đứa trẻ thứ ~j~ thực hiện một chuyến du lịch đi từ thành phố ~u_j~ đến thành phố ~v_j~. Trong quá trình di chuyển, đứa trẻ này có một yêu cầu pha chế nước ép như sau:

• Chỉ được phép mua nguyên liệu tại các thành phố nằm trên đường đi ngắn nhất từ ~u_j~ đến ~v_j~ (bao gồm cả ~u_j~ và ~v_j~).
• Cần mua tổng cộng ít nhất ~L_j~ lít nguyên liệu để pha thành một ly nước ép hỗn hợp.
• Tổng số tiền chi trả cho lượng nguyên liệu được mua không được vượt quá ~g_j~.

Độ ngon của một ly nước ép hỗn hợp được định nghĩa là giá trị nhỏ nhất trong số các độ ngon của những nguyên liệu được chọn để pha chế.

Sau khi một đứa trẻ nhận được nước ép, nó hài lòng và rời khỏi Vùng đất Kỳ diệu ngay lập tức. Khi đó, các thành phố sẽ bước vào trạng thái nạp năng lượng - các thành phố sẽ làm đầy trữ lượng nước ép nếu đã bị sử dụng bởi đứa trẻ vừa thăm quan để chuẩn bị tiếp đón đứa trẻ tiếp theo. Khi đứa trẻ kế tiếp bước vào Vùng đất Kỳ diệu, mọi thành phố đều ở trạng thái đã đầy đủ trữ lượng nước ép tối đa có thể chứa. Nói cách khác, mọi yêu cầu của ~m~ đứa trẻ sẽ độc lập với nhau; trước mỗi yêu cầu, thành phố ~i~ luôn có đủ ~l_i~ lít nguyên liệu, nhằm đảm bảo sự công bằng và giữ lại niềm vui trọn vẹn cho mọi đứa trẻ tham quan Vùng đất Kỳ diệu này.

Yêu cầu: Với mỗi đứa trẻ, hãy xác định cách chọn mua nguyên liệu sao cho thỏa mãn tất cả các điều kiện trên, đồng thời độ ngon của ly nước ép hỗn hợp đạt giá trị lớn nhất có thể. Nếu không có cách nào mua đủ nguyên liệu hoặc chi phí vượt quá giới hạn, hãy trả về kết quả là ~-1~.

Đầu vào

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 10^5~) — lần lượt là số thành phố và số đứa trẻ.
• Trong ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~d_i, p_i, l_i~ (~1 \le d_i, p_i, l_i \le 10^5~) — lần lượt mô tả độ ngon, giá bán mỗi lít và trữ lượng tối đa của nguyên liệu tại thành phố ~i~.
• Trong ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ (~1 \le x, y \le n~) — mô tả một con đường hai chiều nối thành phố ~x~ với thành phố ~y~.
• Trong ~m~ dòng tiếp theo, dòng thứ ~j~ chứa bốn số nguyên ~u_j, v_j, g_j, L_j~ (~1 \le u_j, v_j \le n~; ~1 \le g_j, L_j \le 10^{18}~) — mô tả thành phố xuất phát, thành phố kết thúc, ngân sách và lượng nguyên liệu tối thiểu cần mua của đứa trẻ thứ ~j~.

Đầu ra

Gồm ~m~ dòng, dòng thứ ~j~ in ra một số nguyên duy nhất là độ ngon lớn nhất của ly nước ép hỗn hợp mà đứa trẻ thứ ~j~ có thể nhận được. Nếu không thể đáp ứng yêu cầu, in ra ~-1~.

Giới hạn

• Subtask ~1~ (~7.5\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~7.5\%~ số điểm): ~u_j = v_j~ với mọi ~1 \le j \le m~.
• Subtask ~3~ (~10\%~ số điểm): Cấu trúc mạng lưới là một cây nhị phân hoàn hảo.
• Subtask ~4~ (~15\%~ số điểm): ~p_i = 1~ với mọi ~1 \le i \le n~.
• Subtask ~5~ (~15\%~ số điểm): ~l_i = 1~ với mọi ~1 \le i \le n~.
• Subtask ~6~ (~10\%~ số điểm): Thành phố ~i~ liền kề với thành phố ~i + 1~ với mọi ~1 \le i < n~.
• Subtask ~7~ (~10\%~ số điểm): Mỗi thành phố liền kề với tối đa ~2~ thành phố khác.
• Subtask ~8~ (~25\%~ số điểm): Không có ràng buộc gì thêm.

Ví dụ

Đầu vào

3 2
1 3 5
2 1 3
3 2 5
1 2
2 3
1 3 6 3
1 3 5 3

Đầu ra

3
2

Giải thích

Cấu trúc mạng lưới trong ví dụ là một đường thẳng: thành phố ~1~ nối với thành phố ~2~, thành phố ~2~ nối với thành phố ~3~. Cả hai đứa trẻ đều di chuyển từ thành phố ~1~ đến thành phố ~3~, nên có thể mua nguyên liệu tại cả ba thành phố.

• Với đứa trẻ thứ nhất, ngân sách là ~6~ và cần mua ít nhất ~3~ lít. Để ly nước ép có độ ngon ~3~, chỉ cần mua ~3~ lít nguyên liệu tại thành phố ~3~, với tổng chi phí là ~3 \times 2 = 6~. Do đó, kết quả là ~3~.
• Với đứa trẻ thứ hai, ngân sách là ~5~ và cần mua ít nhất ~3~ lít. Để đạt độ ngon ~3~, phải mua toàn bộ nguyên liệu tại thành phố ~3~, tốn ít nhất ~6~, vượt quá ngân sách. Tuy nhiên, có thể mua ~3~ lít nguyên liệu tại thành phố ~2~ với tổng chi phí là ~3 \times 1 = 3~, thu được ly nước ép có độ ngon ~2~. Do đó, kết quả là ~2~.