Quốc gia \(X\) gồm \(N\) hòn đảo được đánh số từ \(1\) đến \(N\). Các hòn đảo được kết nối với nhau bởi \(N - 1\) cây cầu, các cây cầu này đảm bảo từ một hòn đảo có thể đến được bất kì hòn đảo nào khác. Để kích cầu du lịch tại các hòn đảo, chính quyền đang lên kế hoạch xây dựng một sân bay tại một hòn đảo nào đó sao cho hiệu quả nhất. Biết rằng tại hòn đảo \(i\) có \(D_i\) người sinh sống. Việc có sân bay gần nơi sinh sống sẽ kích thích người dân đi du lịch, do đó chính quyền mong muốn tìm một hòn đảo để xây dựng sân bay sao cho tổng khoảng cách từ tất cả người đân sinh sống trong quốc gia đến sân bay đặt tại hòn đảo này là nhỏ nhất. Khoảng cách của một người đến sân bay gần nhất là tổng khoảng cách nhỏ nhất của các cây cầu cần đi qua từ hòn đảo người đó sinh sống đến hòn đảo có sân bay.

Yêu cầu: Hãy tìm một hòn đảo để xây dựng sân bay sao cho tổng khoảng cách của tất cả người dân đến sân bay là nhỏ nhất.

Input

• Dòng đầu chứa một số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(D_i\) (\(0 \le D_i \le 10^4\)).
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u,v,w\) (\(1 \le u,v \le N, u \neq v, 1 \le w \le 10^4\)) mô tả có cây cầu kết nối hòn đảo \(u\) với hòn đảo \(v\) và có chiều dài là \(w\).

Output

• Ghi ra tổng khoảng cách nhỏ nhất của tất cả người dân đến sân bay.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 300\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \le 3000\).
• Subtask \(3\) (\(50\%\) số điểm): \(N \le 10^5\).

Example

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

20