Minimum Vaccine Distribution Cost

You are given N cities and M bidirectional roads. Each city has an associated setup cost to build a vaccine distribution center. Additionally, a road connecting two cities has a distribution cost. The goal is to ensure every city receives vaccines at the minimum total cost by either setting up a distribution center in that city or by receiving vaccines from a neighboring city through a road.

This problem can be formulated as follows. Define a new node that is connected to every city i with an edge of weight \(a_i\) (the setup cost). Then, by computing the minimum spanning tree (MST) of this augmented graph, you determine the lowest cost required to deliver vaccines to all cities.

Input/Output: Your program should read from standard input (stdin) and output the result to standard output (stdout).

Mathematical Formulation:

Find a subset of edges \(E'\) in the augmented graph such that the total cost \[ \text{Cost} = \sum_{e \in E'} w(e) \] is minimized and all nodes are connected. Here, the weights satisfy \(w(i) = a_i\) for the edge connecting the dummy node to city \(i\), and for each road \(u \leftrightarrow v\) the weight is given by its distribution cost \(w\).

inputFormat

The first line contains two integers \(N\) and \(M\), where \(N\) is the number of cities and \(M\) is the number of roads.

The second line contains \(N\) integers representing the setup costs of the cities: \(a_1, a_2, \dots, a_N\).

The following \(M\) lines each contain three integers \(u, v, w\), indicating there is a road between city \(u\) and city \(v\) with distribution cost \(w\).

You can assume that cities are numbered from 1 to \(N\).

outputFormat

Output a single integer representing the minimum total cost to provide vaccines to all cities.

## sample

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

8