Mạng lưới giao thông trong một quốc gia bao gồm ~N~ thành phố (được đánh số từ ~1~ đến ~N~) và ~N-1~ con đường kết nối chúng theo cách sao cho tất cả các thành phố đều được kết nối. Đối với mỗi con đường, độ dài của nó tính bằng kilômét là đã biết, và trong mỗi thành phố có một trạm xăng với một lượng nhiên liệu nhất định.

Do thiếu hụt nhiên liệu đã ảnh hưởng đến quốc gia một vài năm trước, cơ quan vận tải hàng đầu đã quyết định tiến hành một cuộc khảo sát về khả năng vận chuyển hàng hóa giữa các thành phố. Xe tải vận chuyển hàng tiêu thụ một đơn vị nhiên liệu mỗi kilômét và hành trình giữa hai thành phố láng giềng được coi là có thể nếu lượng nhiên liệu trong bể nhiên liệu của một chiếc xe tải vào thời điểm rời thành phố lớn hơn hoặc bằng khoảng cách giữa các thành phố. Mỗi khi một chiếc xe tải đến một thành phố, bể nhiên liệu của xe tải có thể được nạp đầy một lượng không lớn hơn lượng nhiên liệu tại trạm xăng của thành phố đó.

Đánh giá cuối cùng của cuộc khảo sát được xác định là số cặp thành phố ~(A, B)~ được sắp xếp sao cho có thể di chuyển từ thành phố ~A~ đến thành phố ~B~ dưới điều kiện rằng một chiếc xe tải bắt đầu hành trình với bể nhiên liệu trống (tại điểm xuất phát của hành trình bể nhiên liệu nên được nạp đầy tại trạm xăng ở thành phố ~A~).

Với mục đích nghiên cứu đơn giản hóa, các giả định sau đã được tính đến:

• Bể nhiên liệu của một chiếc xe tải có khả năng không giới hạn.
• Một chiếc xe tải rời khỏi thành phố ~A~ và đi thẳng đến thành phố ~B~, tức là nó không ghé thăm bất kỳ thành phố nào trên hành trình của mình nhiều hơn một lần.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 100,000)~, số lượng thành phố.
• Trong dòng thứ hai là ~N~ số nguyên ~A_i~ ~(1 \leq A_i \leq 10^9)~, lượng nhiên liệu tại trạm xăng của thành phố thứ ~i~.
• Trong ~N-1~ dòng tiếp theo là ba số nguyên ~U, V~ ~(1 \leq U, V \leq N, U \ne V)~ và ~W~ ~(1 \leq W \leq 10^9)~ mô tả con đường giữa các thành phố ~U~ và ~V~ có độ dài ~W~ kilômét.

Output

In ra đánh giá cuối cùng của cuộc khảo sát.

Chú ý

• ~20 \%~ điểm, sẽ có ~N \leq 5000~.
• ~40 \%~ điểm, mạng lưới các thành phố sẽ hình thành một chuỗi, tức là mỗi thành phố ~x~ ~(1 \leq x \leq N)~ sẽ được kết nối với thành phố ~x + 1~.

Sample Input 1

2
3 1
1 2 2

Sample Output 1

1

Sample Input 2

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

Sample Output 2

5

Sample Input 3

8
5 2 4 7 8 3 3 6
6 5 5
1 4 5
3 1 2
8 6 5
1 2 3
4 5 3
4 7 5

Sample Output 3

29

Giải thích

Giải thích cho ví dụ đầu tiên: Cách duy nhất để đi lại là từ thành phố ~1~ đến thành phố ~2~. Hành trình từ thành phố ~2~ đến thành phố ~1~ không thể thực hiện được vì trước khi khởi hành từ thành phố ~2~, một chiếc xe tải không thể có nhiều hơn ~1~ đơn vị nhiên liệu trong bể nhiên liệu.

Giải thích cho ví dụ thứ hai: Các cặp thành phố mà hành trình là có thể thực hiện ~(1, 2)~, ~(3, 2)~, ~(4, 5)~, ~(5, 1)~ và ~(5, 4)~.