Linkedin is organizing a concert in every city of a country. There are N cities numbered from 1 to N, connected by M bidirectional roads.
Each city [i] hosts a concert with a ticket price of A[i].
Each road connects two cities and has a travel cost. If a road connects cities u and v with cost w, traveling across that road in either direction costs exactly w.
For every city i, determine the minimum amount of money required for a person starting from city i to:
Attend exactly one concert in any reachable city (including their own city).
Return back to city i.
If a person attends the concert in their own city, no travel cost is incurred.
It is not guaranteed that every city is reachable from every other city.
Cost Calculation
If a person starts from city i and attends the concert in city j, the total cost is:
Travel Cost (i → j) + A[j] + Travel Cost (j → i)
Since the roads are bidirectional, the return journey has the same travel cost.