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 đỉnh đến được từ 1 và đến được từ \(n\).

Dữ liệu vào: Từ tệp DIEMHEN.INP gồm:

+ Dòng đầu tiên ghi 3 số nguyên \(n,\ m,\ k\) \((2 \leq n \leq 10^{5};1 \leq m \leq {2.10}^{5};1 \leq k \leq 100)\).

+ Dòng thứ \(i\ (i = 1\ldots m)\) trong \(m\) dòng tiếp theo, mỗi dòng ghi 3 số nguyên \(u_{i},\ v_{i},\ c_{i}\) \((1 \leq u_{i},\ c_{i} \leq n;1 \leq c_{i} \leq 10^{6})\).

+ Dòng thứ \(j\ (j = 1\ldots k)\) trong \(k\) dòng tiếp theo, mỗi dòng số nguyên \(a_{i},\ b_{i}\) \((1 \leq a_{i},\ b_{i} \leq 10^{6})\).

Kết quả: Ghi vào tệp DIEMHEN.OUT gồm \(k\) dòng, dòng thứ \(i(i = 1\ldots k)\) cho biết tổng thời gian ít nhất mà hai bạn di chuyển trong ngày thứ \(i\).

Ví dụ:

Giới hạn:

• Có 30% số test tương ứng 30% số điểm có \(2 \leq n \leq 100\).

• Có 30% số test khác tương ứng 30% số điểm có \(n \leq 1000\).

• Có 40% số test khác tương ứng 40% số điểm có: \(n \leq 10^{5}\).