Tổng động viên

Vương quốc Berland có $n$ thành phố được nối với nhau bởi $n-1$ tuyến đường sắt — mỗi tuyến nối đúng hai thành phố khác nhau. Thủ đô nằm ở thành phố $1$, và từ mỗi thành phố đều có thể đi đến thủ đô bằng đường sắt (đồ thị là một cây).

Tại thành phố thứ $i$ đóng quân sư đoàn số $i$, có chỉ số ưu tiên là $a_i$ — giá trị càng nhỏ thì ưu tiên càng cao. Tất cả $a_i$ đôi một khác nhau.

Một ngày nọ, nhà vua ra lệnh tổng động viên: tất cả các sư đoàn phải di chuyển về thủ đô. Mỗi ngày, từ mỗi thành phố khác thủ đô khởi hành đúng một chuyến tàu, đi theo hướng giảm khoảng cách đến thủ đô và mất đúng $1$ ngày để đến thành phố kề tiếp theo. Chuyến tàu đi qua tuyến đường sắt thứ $j$ có sức chứa tối đa $c_j$ sư đoàn.

Khi tàu khởi hành từ một thành phố, trong số các sư đoàn đang có mặt tại thành phố đó, các sư đoàn có $a_i$ nhỏ nhất sẽ lên tàu trước, lần lượt đến khi tàu đầy hoặc hết sư đoàn. Những sư đoàn không lên kịp sẽ ở lại và chờ chuyến tàu ngày hôm sau. Mọi sư đoàn bắt đầu di chuyển cùng lúc; thời gian được tính từ ngày $0$. Khi đến thủ đô, sư đoàn dừng lại tại đó.

Với mỗi sư đoàn, hãy xác định nó đến thủ đô vào ngày thứ mấy.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ — chỉ số ưu tiên của sư đoàn ở từng thành phố.
• $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $v_j,u_j,c_j$ — tuyến đường sắt thứ $j$ nối hai thành phố $v_j$ và $u_j$ với sức chứa tàu $c_j$.

Dữ liệu ra

In ra $n$ số $t_1,t_2,\dots ,t_n$ cách nhau bởi dấu cách, trong đó $t_i$ là số ngày để sư đoàn ở thành phố $i$ đến được thủ đô.

Ràng buộc

• $1\le n\le 5000$.
• $1\le a_i\le {10}^9$, mọi $a_i$ đôi một khác nhau.
• $1\le v_j,u_j\le n$, $v_j\ne u_j$, $1\le c_j\le n$.

Ví dụ