Có ~ n ~ thành phố được đánh số từ 1 đến ~ n ~ và ~ w ~ cửa hàng bán bánh được đánh số từ 1 đến ~ w ~, cửa hàng thứ ~ i ~ được mô tả bởi 3 số ~ c_i, k_i, p_i ~ trong đó ~ c_i ~ là thành phố mà cửa hàng được đặt, ~ k_i ~ là số lượng bánh có trong cửa hàng và ~ p_i ~ là giá của mỗi chiếc bánh.

Có ~ q ~ khách hàng được đánh số từ 1 đến ~ q ~, khách hàng thứ ~ i ~ cũng được mô tả bằng 3 thông số ~ g_i, r_i ~ và ~ a_i ~ trong đó ~ g_i ~ cho biết thành phố mà người thứ i đang ở, ~ r_i ~ là số lượng bánh người thứ ~ i ~ cần và ~ a_i ~ là số tiền mà người thứ ~ i ~ có.

Yêu cầu: Hãy cho biết khoảng cách nhỏ nhất mà người thứ ~ i ~ cần di chuyển để mua được ~ r_i ~ bánh. Nếu không mua được bánh thì ghi ~ -1 ~. Biết rằng việc mua bánh của người này không ảnh hưởng đến người khác.

Dữ liệu vào

• Dòng đầu tiên ghi 2 số nguyên ~ n ~ và ~ m ~ cho biết có ~ n ~ thành phố và ~ m ~ tuyến đường, mỗi tuyến đường nối 2 thành phố khác nhau
• ~ m ~ dòng tiếp theo, mỗi dòng ghi 2 số ~ u ~ và ~ v ~ cho biết có 1 tuyến đường giữa hai thành phố ~ u ~ và ~ v ~ với độ dài bằng 1;
• Dòng tiếp theo ghi số nguyên ~ w ~;
• ~ w ~ dòng tiếp theo dòng thứ ~ i ~ ghi 3 số ~ c_i, k_i, p_i ~;
• Dòng tiếp theo ghi số nguyên ~ q ~;
• ~ q ~ dòng tiếp theo mỗi dòng ghi 3 số ~ g_i, r_i ~ và ~ a_i ~

Kết quả

• Gồm ~ q ~ dòng, mỗi dòng trả lời cho 1 bộ ~ g_i, r_i ~ và ~ a_i ~

Ràng buộc

• ~ 1 ≤ n, w ≤ 5000 ~
• ~ m ≤ min(5000, n*(n-1)/2) ~
• ~ 1 ≤ c_i ≤ n ~
• ~ 1 ≤ k_i, p_i ≤2.10^5 ~
• ~1 ≤ q ≤ 1000 ~
• ~ 1 ≤ g_i ≤ n ~
• ~ 1 ≤ r_i, a_i ≤ 10^9 ~

Ví dụ:

Input 1

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

Output 1

2
-1
2
2
3
-1