Minimum Cost Path

The country of Hackerland is represented as a graph of g_nodes cities numbered from 1 to g_nodes . The cities are connected through g_edges bidirectional roads where the i-th road connects city g_from[i] to city g_to[i] and the amount of fuel required to travel a road is g_weight[i] units. The cars in Hackerland has infinite fuel capacity. The cost of one unit of fuel in the ith city is arr[i]. Any amount of fuel can be obtained in any city. Given two cities A and B (1<=A,B<=road_nodes) , find the minimum cost to travel city A to city B. Note: All the cities must be visited atleast once. If it's not possible then return -1.

Example:

g_nodes = 5 g_from = [4,5,4,1,3,4,4] g_to = [1,3,5,5,1,2,3] g_weight = [1,1,8,1,3,9,5] arr = [9,11,3,2,10] A=3 B=2

Output: 27

Explanation: One optimal path is 3 -> 5 -> 1 -> 4 -> 2. Buy 3 units of fuel at 3 with a cost of 3x3=9 and 9 units at city 4 for 9x2 = 18. The total cost is 9+18=27.

int g_nodes: the number of cities int g_from[g_edges]: one endpoint of each road int g_to[g_edges]: the other endpoint of each road int g_weight[g_edges]: the weight of each road int arr[g_nodes]: the cost of unit city in each fuel int A : the city to start from int B: the destination city

Input format:

The first line contains two integers g_nodes and g_edges, the number of cities and bidirectional roads connecting them. Each line i of the g_edges subsequent lines (where 1<=i<g_edges) contains three integers , g_from[i], g_to[i] and g_weight[i]. The next line contains the same integer, g_nodes, the size of arr. Each line i of the g_nodes subsequent lines (where 1<=i<g_nodes) contains an integer , arr[i]. The next line contains the integer A. The last line contains the integer B.

Example:

Input:
    4 3
    1 2 3
    2 3 1
    2 4 7
    4
    3
    6
    2
    2
    1
    4

Output: 28

Some one please give the code for this problem. Thanks.