Operation "Steak or Boiling"
The marketing team at "std::steak" has launched a new advertising campaign called "Steak or Boiling." The goal of this project is to dominate the entire market in Berlandia. Teams of agents will visit every house in every city, posing the absurd question: "Steak or Boiling?". Through this strategy, the company aims to intimidate competitors and bewilder potential customers.
Agent teams will be deployed by air to certain cities in Berlandia. From there, they must travel by road to visit all the cities in the country. The cities are linked by one-way roads, each with a specified length. In any city, the teams can split up as needed (the initial number of agents is very large).
The cost of traveling along a road is equal to its length. Additionally, each city has a known cost for organizing a landing.
What is the minimum budget required for the "Steak or Boiling" operation?
Input
The input consists of one or more sets of data.
The first line of each set contains two integers N and M (1 ≤ N ≤ 300, 0 ≤ M ≤ N^2-N), where N is the number of cities in Berlandia, and M is the number of roads. The second line provides the sequence A_1, A_2, ..., A_N, where A_i is the cost of landing in city i (1 ≤ A_i ≤ 1000). Following this, M lines describe the roads with triples of numbers X_i, Y_i, L_i, where X_i is the starting city, Y_i is the destination city, and L_i is the road length (1 ≤ X_i, Y_i ≤ N, X_i ≠ Y_i, 1 ≤ L_i ≤ 1000). There is at most one road in each direction between any pair of cities.
The total sum of N across all input sets does not exceed 300.
Output
For each set of input data, output the minimum required budget.