Cho cây ~T~ gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~ và các cạnh được đánh số từ ~1~ đến ~n-1~. Cạnh thứ ~i~ của cây nối hai đỉnh ~u_i~ và ~v_i~ với trọng số ~w_i~. Mỗi đỉnh ~x~ của cây đều được gán một trọng số ~a_x~.

Hàm ~d(u,v)~ được định nghĩa là độ dài đường đi ngắn nhất giữa hai đỉnh ~u~ và ~v~ trên cây.

Hàm ~f(u,v)~ được định nghĩa như sau:

~f(u,v)=d(u,v)+a_u+a_v~

Xét đơn đồ thị ~G~ bao gồm ~n~ đỉnh và ~\frac{n(n-1)}{2}~ cạnh, giữa hai đỉnh ~u~ và ~v~ ~(u \neq v)~ của đồ thị ~G~ có trọng số ~f(u,v)~. Bạn hãy tìm độ dài cây khung nhỏ nhất của ~G~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \le n \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i~ và ~w_i~ mô tả cạnh thứ ~i~ của cây ~(1 \le u_i,v_i \le n~ ~;~ ~1 \le w_i \le 10^9)~.
• Dữ liệu đảm bảo các cạnh đã cho tạo thành một cây hợp lệ.

Output

• In ra độ dài cây khung nhỏ nhất của đồ thị ~G~.

Examples

Sample Input 1

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

Sample Output 1

22

Sample Input 2

6
44 23 31 29 32 15
4 5 8
2 1 10
6 4 15
3 1 12
1 4 16

Sample Output 2

359

Notes

Trong ví dụ đầu tiên, các giá trị ~f(u,v)~ như sau:

• ~f(1,2)=5~
• ~f(1,3)=9~
• ~f(1,4)=8~
• ~f(2,3)=10~
• ~f(2,4)=9~
• ~f(3,4)=9~