N cities are connected using bidirectional roads (there may be multiple roads between two cities and the graph may not be fully connected).

There is a value associated with each nodes (A[i]) and with each edges. The cost of entering a city is A[i].

We have to find the minimum cost of entering any city starting from every possible element i.

Example :

4 cities having value (5, 7, 100, 11) and roads are (u, v, w) where (u, v) are nodes and w is the weight of the edge.

(1, 2, 5), (3, 4, 50)

Answer is (5, 7, 61, 11)

Explanation : starting from 1 we can enter city 1 (cost 5)

starting from 2 we can enter city 2 (cost 7)

starting from 3 we can enter city 4 (cost: (3 -> 4)edge + value_of_entering_4(11) = 61)

starting from 4 we can enter city 4 (cost: 11)

**Constraints**:

All the edge values and cost of entering a city is <= 10^9

Number of cities and number of roads <= 10^5