Given a graph consisting of N vertices and M edges. There is a treasure on every vertex of the graph which has a price of A[i] and weight of Bli]. For each vertex v you have to determine the minimum cost to collect the treasure from any vertex u (u may or may not be egaul to v). The cost for vertex v to collect the treasure from u has mainly four components.

1. The price A[u] of the treasure at vertex u.

2. The sum of weights of all the edges in the path from v to u

3. The sum of weights of all the edges in the path from u to v

4. An additional cost of X*B[u] is also added, where X is the number of edges traversed on the path from u to v

Notes

1. The ith bidirectional edge goes from C[i][0] to C[i][1] and has a weight of C[i][2] 2. The path to go from v to u and to comeback to v from u may or may not be same.

3 There might be multiple edges and self loops

Problem Description Given a graph consisting of N vertices and M edges. There is a treasure on every vertex of the graph which has a price of A[i] and weight of B[i]. For each vertex v you have to determine the minimum cost to collect the treassure fromi any vertex u (u may or may not be eqaul to v ). The cost for vertex v to collect the treasure from u has mainly four components. 1. The price A[a] of the titreasure lat vertex . 2. The sum of weightsiof all the edges in the path from vi to u. 3. The sum of weights of all the edges in the path from u to v. 4. An additional cost of XB[u ) is alsol ladded, where X is the number of edges traversed on the path from u to v. Notes 1. The ith bidirectional edge goes from c[i][0] to Cli] [1] and has a weight of C[i][2]. 2. The path to go from v to u and to to comeback to v from u may or may not be same. 3. There might be multiple,edges and selfilaops, Problem Constraints 1=N