Shortest Path Within Maximum Travel Time

You are given a graph representing a network of cities connected by roads. Each road has an associated travel time. Your task is to determine the shortest travel time from a starting city (the capital) to a target city, under the constraint that the travel time does not exceed a given maximum value T. If the target city cannot be reached within T time units, output -1.

The graph G consists of n cities and m roads. Roads are bidirectional. The input format is defined as follows below.

The answer should be computed using Dijkstra's algorithm (or an equivalent method), and care must be taken to only consider routes where the total travel time is \(\le T\). The solution should be implemented to read from standard input (stdin) and output the result on standard output (stdout).

inputFormat

The first line of the input contains five space-separated integers: \(n\), \(m\), \(T\), \(c\), and \(t\), where:

• \(n\) is the number of cities.
• \(m\) is the number of roads.
• \(T\) is the maximum allowed travel time.
• \(c\) is the starting city (capital).
• \(t\) is the target city.

Then, \(m\) lines follow. Each of these lines contains three space-separated integers \(u\), \(v\), and \(w\) representing a road between cities \(u\) and \(v\) with travel time \(w\).

outputFormat

Output a single integer which is the minimum travel time from city \(c\) to city \(t\) if such a route exists within the allowed maximum travel time \(T\); otherwise, output -1.

5 7 15 1 5
1 2 4
1 3 2
2 3 5
2 4 10
3 4 3
4 5 7
3 5 12

12