Transport

Το δίκτυο κυκλοφορίας σε μία χώρα αποτελείται από ~N~ πόλεις (σημειωμένες με αριθμούς από το 1 έως το ~N~) και από ~N-1~ δρόμους που τις συνδέουν με τρόπο τέτοιο, που συνδέονται όλες οι πόλεις. Για κάθε δρόμο είναι γνωστό το μήκος του σε χιλιόμετρα και σε κάθε πόλη υπάρχει βενζινάδικο με συγκεκριμένη ποσότητα καυσίμου.

Λόγω των ελλείψεων καυσίμων που έπληξαν τη χώρα πριν από μερικά χρόνια, το κορυφαίο πρακτορείο μεταφορών αποφάσισε να πραγματοποιήσει έρευνα για τη δυνατότητα μεταφοράς εμπορευμάτων μεταξύ πόλεων. Τα φορτηγά που μεταφέρουν εμπορεύματα καταναλώνουν μία μονάδα καυσίμου ανά χιλιόμετρο και η διαδρομή μεταξύ δύο γειτονικών πόλεων θεωρείται δυνατή εάν η ποσότητα καυσίμου στη δεξαμενή καυσίμου ενός φορτηγού τη στιγμή της αναχώρησης από την πόλη είναι μεγαλύτερη ή ίση με την απόσταση μεταξύ των πόλεων. Κάθε φορά που ένα φορτηγό βρίσκεται σε μια πόλη, η δεξαμενή καυσίμου του φορτηγού μπορεί να γεμίσει με ποσότητα όχι μεγαλύτερη από την ποσότητα καυσίμου στο βενζινάδικο της πόλης. Η τελική αξιολόγηση της έρευνας ορίζεται ως ο αριθμός των ζευγών πόλεων ~(A, B)~, έτσι ώστε να είναι δυνατό να ταξιδέψετε από την πόλη ~A~ στην πόλη ~B~ με την υπόθεση ότι ένα φορτηγό ξεκινά το ταξίδι με άδεια δεξαμενή καυσίμου (στην αρχή του ταξιδιού το ρεζερβουάρ καυσίμου πρέπει να γεμίσει στο βενζινάδικο της πόλης ~A~).

Για την απλούστευση της έρευνας έχουν ληφθεί υπόψη οι ακόλουθες παραδοχές:

• Η δεξαμενή καυσίμου ενός φορτηγού έχει απεριόριστη χωρητικότητα.
  
• Ένα φορτηγό που φεύγει από την πόλη ~A~ ταξιδεύει απευθείας στην πόλη ~B~, δηλαδή δεν επισκέπτεται καμία πόλη στο ταξίδι του περισσότερες από μία φορές.

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό ~N~ (~1 \le N \le 100\,000~), τον αριθμό των πόλεων.
Στη δεύτερη γραμμή υπάρχουν ~N~ ακέραιοι αριθμοί ~A_i~ (~1 \le A_i \le 10^9~), η ποσότητα καυσίμου στο βενζινάδικο στην i-οστή πόλη.
Στις ακόλουθες ~N-1~ σειρές υπάρχουν τρεις ακέραιοι αριθμοί ~U, V\;(1 \le U, V \le N, U \ne V)~ και ~W\;(1 \le W \le 10^9)~, που περιγράφουν το δρόμο μεταξύ των πόλεων ~U~ και ~V~, μήκους ~W~ km.

Έξοδος

Τυπώστε την τελική αξιολόγηση της έρευνας.

Βαθμολογία

Σε περιπτώσεις δοκιμής συνολικής αξίας 20% των πόντων θα ισχύει ~N \le 5\,000~
Σε περιπτώσεις δοκιμής συνολικής αξίας 40% των πόντων, το δίκτυο των πόλεων θα σχηματίσει μια αλυσίδα, δηλαδή κάθε πόλη ~x\;(1 \le x < N)~ θα συνδέεται με την πόλη ~x+1~.

Παραδείγματα

input

2
3 1
1 2 2

output

1

Επεξήγηση του 1ου παραδείγματος:

Ο μόνος δυνατός τρόπος να ταξιδέψετε είναι από την πόλη 1 στην πόλη 2. Η διαδρομή από την πόλη 2 στην πόλη 1 δεν είναι δυνατή γιατί πριν την αναχώρηση από την πόλη 2 ένα φορτηγό δεν μπορεί να έχει περισσότερες από 1 μονάδα καυσίμου στη δεξαμενή καυσίμων.

input

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

output

5

Επεξήγηση του 2ου παραδείγματος:

Ζεύγη πόλεων μεταξύ των οποίων το ταξίδι είναι εφικτό ~(1, 2), (3, 2), (4, 5), (5, 1)~ και ~(5, 4)~.

input

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

output

29