Đường đi tốt nhất

Một đất nước có $n$ thành phố, được nối với nhau bởi $n-1$ con đường hai chiều sao cho từ thành phố bất kỳ có thể đi tới mọi thành phố khác (hệ thống đường tạo thành một cây).

Mỗi thành phố $i$ có một trạm xăng, và do quy định của địa phương, tại thành phố $i$ bạn chỉ được mua đúng $w_i$ lít xăng. Mỗi con đường có một độ dài $c$, và mỗi lần đi qua con đường đó, lượng xăng trong bình giảm đi $c$ lít.

Bạn cần chọn một thành phố xuất phát $u$ và một thành phố kết thúc $v$, rồi đi theo đường đi đơn (không lặp lại thành phố nào) từ $u$ tới $v$. Đường đi có thể chỉ gồm một thành phố duy nhất ($u=v$). Bạn mua xăng tại mọi thành phố đi qua, kể cả thành phố xuất phát và thành phố kết thúc. Lượng xăng ban đầu bằng $0$ và trong suốt hành trình lượng xăng không bao giờ được âm, tức là không được chọn đường đi mà giữa chừng bị hết xăng.

Hãy tính lượng xăng lớn nhất còn lại trong bình khi kết thúc hành trình.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số thành phố.
• Dòng thứ hai chứa $n$ số nguyên $w_1,w_2,\dots ,w_n$ là lượng xăng mua được tại mỗi thành phố.
• $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$, $c$ mô tả một con đường nối thành phố $u$ và thành phố $v$ có độ dài $c$.

Dữ liệu ra

Một số nguyên duy nhất là lượng xăng lớn nhất còn lại khi kết thúc hành trình.

Ràng buộc

• $1\le n\le 3·{10}^5$
• $0\le w_i\le {10}^9$
• $1\le u,v\le n$, $u\ne v$, $1\le c\le {10}^9$
• Dữ liệu đảm bảo hệ thống đường tạo thành một cây.

Ví dụ