Giải bài trực tuyến

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ủ đô.

INPUT

5

1 2 20

2 3 12

2 4 1

4 5 3

26 9

1 10

500 2

2 30

OUTPUT

206 321 542 328

Giới hạn:

• 3 ≤ N ≤ 100 000, 0 ≤ S_i ≤ 10⁹, 1 ≤ V_i ≤ 10⁹
• Độ dài không vượt quá 10 000.