Minimum Cost TIP Network

King Byteasar wants to build a network of Tourist Information Points (TIPs) in Byteotia. There are n towns and m bidirectional roads, each connecting two distinct towns. Due to the sparse road network, it is observed that wherever one starts a journey, it is impossible to visit more than 10 towns without re‐entering a town.

To boost tourism despite the short available routes, the king has decided that each town must have a TIP either in the town itself or in one of its directly adjacent towns. Each town has a building cost for a TIP. Your task is to help the king determine the minimum total cost for constructing TIPs so that every town is covered.

The condition for coverage can be stated mathematically as follows. For every town i (for i=1,...,n), let N(i) be the set consisting of town i and all towns directly connected to i by a road. Then, a set S ⊆ {1,...,n} is a valid solution if for every i there exists some j ∈ N(i) such that j ∈ S. You must choose S so that the total cost \( \sum_{j \in S} c_j \) is minimized, where \( c_j \) is the cost for building a TIP in town \( j \).

inputFormat

The input begins with two integers n and m (number of towns and roads respectively).

The next line contains n integers, where the i-th integer denotes the cost of building a TIP in town i.

Then follow m lines, each containing two integers u and v, indicating that there is a bidirectional road connecting town u and town v. Town indices are 1-based.

outputFormat

Output a single integer, the minimum total cost to build TIPs such that every town is either equipped with a TIP or has a neighboring town with a TIP.

sample

3 2
1 2 3
1 2
2 3

2