Ngày xửa ngày xưa, có ~N~ thị trấn kiểu trung cổ trong khu tự trị Moldavian. Các thị trấn này được đánh số từ ~1~ đến ~N~. Thị trấn ~1~ là thủ đô. Các thị trấn được nối với nhau bằng ~N -1~ con đường hai chiều, mỗi con đường có độ dài được đo bằng km. Có duy nhất một tuyến đường nối giữa hai điểm bất kỳ (đồ thị các con đường là hình cây). Mỗi thị trấn không phải trung tâm có một người truyền tin.

Khi một thị trấn bị tấn công, tình hình chiến sự cần được báo về thủ đô càng sớm càng tốt. Một thông điệp được truyền bằng các người truyền tin. Mỗi người truyền tin được đặc trưng bởi lượng thời gian khởi động và vận tốc không đổi sau khi xuất phát.

Thông điệp luôn được truyền trên con đường ngắn nhất đến trung tâm. Ban đầu, thông tin chiến sự được đưa cho người truyền tin tại thị trấn bị tấn công. Từ thị trấn đó người truyền tin sẽ đi theo con đường về gần thủ đô hơn. Khi đến một thị trấn mới, người truyền tin có thể đi tiếp hoặc chuyển cho người truyền tin tại thị trấn mới vừa đến. Lưu ý rằng khi chuyển sang người truyền tin mới thì người này cần một lượng thời gian để khởi động rồi mới đi chuyển tin. Như vậy, thông điệp sẽ được chuyển bằng một số người truyền tin trước khi đến thủ đô.

Hãy xác định thời gian ít nhất cần chuyển tin từ các thị trấn về thủ đô.

Input

• Dòng đầu ghi số ~N~. Trong ~N -1~ dòng tiếp theo, mỗi dòng ghi ba số ~u~, ~v~ và ~d~ thể một con đường nối từ ~u~ đến ~v~ với độ dài bằng ~d~.
• Trong ~N -1~ dòng tiếp theo, dòng thứ ~i~ ghi hai số ~S_{i}~ và ~V_{i}~ thể hiện thời gian cần để khởi động và số lượng phút để đi được ~1~ km của người truyền tin ở thị trấn ~(i + 1)~.

Output

• Ghi ~N -1~ số trên một dòng. Số thứ ~i~ thể hiện thời gian ít nhất cần truyền tin từ thành phố ~(i + 1)~ về thủ đô.

Giới hạn

• ~3 \leq N \leq 100\,000~, ~0 \leq S_{i} \leq 10^{9}~, ~1 \leq V_{i} \leq 10^{9}~
• Độ dài không vượt quá ~10\,000~.

Sample Input

5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

Sample Output

206 321 542 328