Sau khi đính hôn với Hoàng tử, hàng ngày cô Tấm và Hoàng tử hẹn gặp nhau để bàn về kế hoạch tổ chức đám cưới. Bản đồ giao thông của vương quốc gồm 𝑛 địa điểm đánh số từ 1 tới 𝑛 và 𝑚 con đường hai chiều đánh số từ 1 tới 𝑚. Con đường thứ 𝑖 nối giữa hai địa điểm 𝑢𝑖 , 𝑣𝑖 và có độ dài 𝑤𝑖 km. Hệ thống giao thông đảm bảo có đường đi từ 1 tới 𝑛.

Nhà của Tấm ở địa điểm 1 còn hoàng cung, nơi hoàng tử ở là địa điểm 𝑛. Hàng ngày họ muốn gặp nhau ở một địa điểm nào đó trong 𝑛 địa điểm đã cho. Khi đã xác định điểm hẹn, hai người sẽ xuất phát cùng lúc (tại thời điểm 0) mỗi người đi từ nhà mình tới điểm hẹn theo con đường ngắn nhất. Người đến điểm hẹn trước sẽ phải chờ người đến sau. Với mỗi ngày, tùy theo phương tiện giao thông mà họ lựa chọn, bạn được cho biết tốc độ di chuyển của từng người. Hãy xác định điểm hẹn cho cuộc gặp gỡ ngày hôm đó sao cho hai người có thể gặp nhau tại thời điểm sớm nhất.

Yêu cầu: Bạn cần tìm giải pháp cho 𝑘 ngày (đánh số từ 1 tới 𝑘). Trong ngày thứ 𝑗, Tấm đi mỗi km mất 𝑎𝑗 giây và Hoàng tử đi mỗi km mất 𝑏𝑗 giây. Hãy cho biết 𝑐𝑗 là thời điểm sớm nhất hai người có thể gặp nhau trong ngày thứ 𝑗. (∀𝑗 = 1,2, … , 𝑘) .

Input:

-Dòng 1 chứa 3 số nguyên 𝑛, 𝑚, 𝑘 (2 ≤ 𝑛 ≤ 10^5; 1 ≤ 𝑚 ≤ 2.10^5; 1 ≤ 𝑘 ≤ 10^5),

-𝑚 dòng tiếp theo, dòng thứ 𝑖 chứa ba số nguyên 𝑢𝑖 , 𝑣𝑖 , 𝑤𝑖 (1 ≤ 𝑢𝑖 , 𝑣𝑖 ≤ 𝑛;1 ≤ 𝑤𝑖 ≤ 10^6).

-𝑘 dòng tiếp theo, dòng thứ 𝑗 chứa hai số nguyên 𝑎𝑗, 𝑏𝑗 (1 ≤ 𝑎𝑖 , 𝑏𝑖 ≤ 10^6)

Ouput:

Ghi 𝑘 số nguyên 𝑐1, 𝑐2, … , 𝑐𝑘 mỗi số trên một dòng.

Sample Input

6 6 2 
1 2 1 
1 5 6 
2 3 2 
3 4 3 
4 6 4 
5 6 1 
7 4 
1 6

Sample Output

28
6