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$$$