Quốc gia “AI - CodeDream” có ~N~ thành phố và ~N - 1~ con đường đảm bảo việc giữa 2 thành phố bất kì luôn có đúng 1 đường đi giữa chúng.

Con đường thứ ~j~ nối hai thành phố ~u[j]~ và ~v[j]~ với thời gian để đi qua con đường là ~w[j]~.

Hôm nay, Purple đến thăm những người bạn của mình ở AI - CodeDream.

Nếu Purple đi qua thành phố thứ ~i~ thì anh sẽ ở lại đó thời gian là ~c[i]~.

Purple rất muốn tối đa thời gian ở AI - CodeDream của mình nhưng anh là một người rất liêm nên anh quyết định không đi lại con đường nào quá 1 lần.

Yêu cầu

Bạn hãy giúp Purple tính xem với mỗi thành phố ~i~, nếu anh muốn đi qua thành phố này thì tổng thời gian tối đa anh có thể ở AI - CodeDream là bao nhiêu.

(Lưu ý : đáp án của thành phố ~i~ là đường đi chỉ cần đi qua ~i~ chứ không cần xuất phát tại ~i~).

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \leq N \leq 10^5)~;
• Dòng thứ hai gồm ~N~ số biểu diễn mảng ~c~ ~(0 \leq c[i] \leq 10^4)~;
• ~N - 1~ dòng tiếp theo mỗi dòng gồm ba số ~u~, ~v~, ~w~ biểu diễn một con đường ~(u, v \leq N; 0 \leq w \leq 1e4)~.

Output

Gồm ~N~ số nguyên trên cùng một dòng, hai số cách nhau bởi một dấu cách.

Số thứ ~i~ biểu diễn thời gian tối đa có thể có khi phải đi qua thành phố ~i~.

Sample Input

5
1 2 3 4 5
1 2 1
2 3 6
2 4 2
4 5 1

Sample Output

16 23 23 23 23

Giải thích

• Với ~i = 1~, ta sẽ chọn đường đi ~1 - 2 - 4 - 5~, thời gian sẽ là ~1 + 1 + 2 + 2 + 4 + 1 + 5 = 16~.
• Với ~i = 2, 3, 4, 5~, ta sẽ chọn đường đi ~3 - 2 - 4 - 5~, thời gian sẽ là ~3 + 6 + 2 + 2 + 4 + 1 + 5 = 23~.

Subtask

• Có 10% số test ứng với 10% số điểm có ~u[j] + 1 = v[j]~ với mọi ~j~;
• Có 20% số test ứng với 20% số điểm có ~N \leq 15~;
• Có 30% số test ứng với 30% số điểm có ~N≤10^3~;
• 40% số test còn lại tương ứng với 40% số điểm không có giới hạn gì thêm.