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.
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)
All the edge values and cost of entering a city is <= 10^9
Number of cities and number of roads <= 10^5