The traffic network in one country consists of cities (marked by numbers from
to
) and
roads connecting them in a way that all cities are connected. For each road, its length in kilometers is known, and in each city there is a gas station with a certain amount of fuel.
Due to the fuel shortages that hit the country a few years ago, the leading transport agency has decided to conduct a survey on the ability to transport goods between cities. Trucks transporting goods consume one unit of fuel per kilometer and the journey between two neighboring cities is considered possible if the amount of fuel in a truck's fuel tank at the time of leaving the city is greater than or equal to the distance between the cities. Each time when a truck is in a city, the truck's fuel tank can be filled up by an amount not greater than the amount of fuel in that city's gas station. The final assessment of the survey is defined as the number of ordered pairs of cities such that it is possible to travel from city
to city
under the assumption that a truck starts the journey with an empty fuel tank (at the beginning of the journey the fuel tank should be filled at the gas station in city
).
For the simplicity of the research, the following assumptions have been taken into account:
- A truck's fuel tank has unlimited capacity.
- A truck leaving from the city
travels directly to the city
, i.e. it does not visit any city on its journey more than once.
Input
The first line contains the integer number
, the number of cities.
In the second line there are integer numbers
, the amount of fuel at the gas station in the
city.
In the following rows there are three integer numbers
and
describing the road between cities
and
of length
kilometers.
Output
Print the final assessment of the survey.
Scoring
In the test samples totally worth 20% of the points it will hold .
In the test samples totally worth 40% points the network of cities will form a chain, i.e. each city
will be connected to city
.
Sample Input 1
2
3 1
1 2 2
Sample Output 1
1
Explanation for Sample Output 1
The only possible way to travel is from city to city
. The journey from city
to city
is not possible because before departure from city
a truck cannot have more than
unit of fuel in the fuel tank.
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
Explanation for Sample Output 2
Pairs of cities among which the journey is possible ,
,
,
and
.
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
Comments