European Trip

A traveler is planning a trip through Europe. There are N countries to visit, numbered from 1 to N, and P bidirectional roads between them.

Before traveling, the traveler may remove roads from the map as long as all countries remain connected. Equivalently, the traveler will keep exactly N-1 roads that connect every country.

Each time a road is used, its road cost is paid. Each time the traveler arrives at a country, that country's visit cost is also paid. The first country is chosen freely, and its visit cost is paid at the start. Roads and countries may be visited multiple times, and the trip must end at the same country where it started.

Find the minimum possible total cost to visit every country at least once and return to the starting country.

The first line contains two integers N and P: the number of countries and the number of roads. The constraints are 5 <= N <= 10,000 and N-1 <= P <= 100,000.

The next N lines contain the visit costs. The i-th of these lines contains C_i, the cost paid whenever country i is reached. Each cost satisfies 1 <= C_i <= 1,000.

The next P lines each contain three integers S_j, E_j, and L_j, meaning that traveling along the road between countries S_j and E_j costs L_j. The endpoints are distinct, and 0 <= L_j <= 1,000.

Print the minimum total cost needed to complete the trip.

In a chosen tree of roads, any closed trip that visits every country must traverse each kept road twice. The starting country contributes one extra visit cost, so choosing a cheapest country as the start is optimal.