HARBINGE - Harbingers

Giới hạn
  • Thời gian: 0.808s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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 9 , 1 ≤ V i ≤ 10 9
  • Độ dài không vượt quá 10 000.

  • Người up: huy391992
  • Nguồn bài: CEOI 2009