Hệ thống giao thông thành phố nơi hai bạn Bình và An sống có ~ n ~ nút giao thông được đánh số từ 1 đến ~ n ~ và ~ m ~ con đường một chiều trong đó con đường thứ ~ i ~ nối nút ~ u_i ~ đến nút ~ v_i ~ có độ dài ~ c_i ~ km.

Hằng ngày, Bình và An hẹn nhau ở một nút giao thông để cùng nhau đến trường sao cho tổng thời gian di chuyển của hai bạn ít nhất. Bình sẽ di chuyển từ nút giao thông 1, An di chuyển từ nút giao thông ~ n ~ và cả hai bạn xuất phát cùng một thời điểm theo con đường ngắn nhất của mình.

Yêu cầu: Bạn cần tìm giải pháp cho ~ k ~ ngày (các ngày được đánh số từ 1 đến ~ k ~). Với ngày thứ ~ i ~ tổng thời gian di chuyển ít nhất của Bình và An là bao nhiêu giây? Biết rằng, ngày thứ ~ i ~ ~ (i = 1..k) ~ Bình di chuyển mỗi km mất ~ a_i ~ giây, An di chuyển mỗi km mất ~ b_i ~ giây. Dữ liệu luôn đảm bảo có ít nhất 1 nút đến được từ 1 và đến được từ ~ n ~.

Dữ liệu vào

• Dòng đầu tiên ghi 3 số nguyên ~ n, m, k ~ ~ (2 ≤ n ≤ 10^5; 1 ≤ m ≤ 2.10 5; 1 ≤ k ≤ 100) ~.
• Dòng thứ ~ i ~ ~ (i = 1…m) ~ trong ~ m ~ dòng tiếp theo, mỗi dòng ghi 3 số nguyên ~ u_i, v_i, c_i ~ ~ ( 1 ≤ u_i, c_i ≤ n; 1 ≤ c_i ≤ 10^6 ) ~.
• Dòng thứ j (j=1…k) trong k dòng tiếp theo, mỗi dòng số nguyên a_i,b_i (1≤a_i,b_i≤10^6).

Kết quả

• Gồm ~ k ~ dòng, dòng thứ ~ i ~ ~ (i = 1…k) ~ cho biết tổng thời gian ít nhất mà hai bạn di chuyển trong ngày thứ ~ i ~.

Ràng buộc

• Có 30% số test tương ứng 30% số điểm có ~ 2 ≤ n ≤ 100 ~.
• Có 30% số test khác tương ứng 30% số điểm có ~ n ≤ 1000 ~.
• Có 40% số test khác tương ứng 40% số điểm có: ~ n ≤ 10^5 ~

Ví dụ:

Input 1

4 4 2
1 2 2
1 3 9
4 2 8
4 3 3
7 3
3 6 

Output 1

38
45