Statement

There are N cities and M bidirectional railways connecting cities a_i and b_i with a travel time of c_i minutes. There is also a train that connects city 0 with city N-1, this train will always take the only shortest path between the two cities. However, the train only passes through some cities and the mayors of the cities it doesn't pass through are angry. To please the mayors, you can upgrade a single railway to high-speed railway, which will reduce the travel time by 1 minute for each euro spent. Of course, the travel time must be strictly positive after the upgrade. You want to upgrade a railway so that the new shortest path between city 0 and city N-1 always passes to at least a city that wasn't passed by the train before. In the new railway network there may be many shortest paths, however the original one must not be one of them. What is the minimum amount of money you need to spend to achieve this?