Question

There are N cities numbered 1 to N connected by M bi directional roads. A concert is going to be organized in each city and in ith city it costs A[i] amount. Every time you travel the ith road connecting B[i][0] and B[i][1] city, it will cost B[i][2] amount. For each city i: 1 to N, find the minimum amount a person from city i has to pay to visit a concert in any of the city and come back to his own city. It may not be guaranteed that each city is reachable from other city.

Problem Constraints

1<= N <= 10^5

0 <= M <= 2*10^5

1<= A[i], B[i][2] <= 10^9

1<= B[i][0], B[i][1] <= N

Input Format

First argument is an integer array A of size N denoting the cost of concert.

Second argument is a 2D array B of sixe M x 3 denoting the road where ith road between B[i][0] and B[i][1] city cost B[i][2] amount.

Output Format

Return an integer array of size N where ith element of the array denotes the minimum amount a person of ith city has to pay to vist a concert​

Answer 1

Answer:

Problem Constraints

1<= N <= 10^5

0 <= M <= 2*10^5

1<= A[i], B[i][2] <= 10^9

1<= B[i][0], B[i][1] <= N

Input Format

First argument is an integer array A of size N denoting the cost of concert.

Second argument is a 2D array B of sixe M x 3 denoting the road where ith road between B[i][0] and B[i][1] city cost B[i][2] amount.

Output Format

Return an integer array of size N where ith element of the array denotes the minimum amount a person of ith city has to pay to vist a concert.