Jack has just moved to a new city called Rapture. He wants to use the public public transport system. The fare rules are as follows:
- Each pair of connected stations has a fare assigned to it regardless of direction of travel.
- If Jack travels from station A to station B, he only has to pay the difference between (the fare from A to B) and (the cumulative fare paid to reach station A), [fare(A,B) - total fare to reach station A]. If the difference is negative, travel is free of cost from A to B.
Jack is low on cash and needs your help to figure out the most cost efficient way to go from the first station to the last station. Given the number of stations (numbered from to ), and the fares (weights) between the pairs of stations that are connected, determine the lowest fare from station to station .
Example
The graph looks like this:
Travel from station costs for the first segment () then the cost differential, an additional for the remainder. The total cost is .
Travel from station costs for the first segment, then an additional for the remainder, a total cost of .
The lower priced option costs .
Function Description
Complete the getCost function in the editor below.
getCost has the following parameters:
- int g_nodes: the number of stations in the network
- int g_from[g_edges]: end stations of a bidirectional connection
- int g_to[g_edges]: is connected to at cost
- int g_weight[g_edges]: the cost of travel between associated stations
Prints
- int or string: the cost of the lowest priced route from station to station or NO PATH EXISTS. No return value is expected.
Input Format
The first line contains two space-separated integers, and , the number of stations and the number of connections between them.
Each of the next lines contains three space-separated integers, and , the connected stations and the fare between them.
Constraints
Sample Input 1
5 5
1 2 60
3 5 70
1 4 120
4 5 150
2 3 80
Sample Output 1
80
Sample Input 2
5 6
1 2 30
2 3 50
3 4 70
4 5 90
1 3 70
3 5 85
Sample Output 2
85