Shortest Route in the Mountains

You are given a network of mountain peaks connected by bidirectional paths. Each path has an associated difficulty level. You need to determine the shortest distance from a starting peak p1 to a destination peak p2, but you can only use the paths whose difficulty does not exceed a given threshold d.

The input starts with five integers: n, m, p1, p2, and d, where n is the number of peaks, m is the number of paths, p1 is the starting peak, p2 is the destination peak, and d is the maximum allowable difficulty. Following this, there are m lines each containing three integers x, y, and t that describe a bidirectional path from peak x to peak y with difficulty t.

If there exists a route from p1 to p2 such that every used path has difficulty no more than d, output the shortest total distance (sum of the path weights). Otherwise, output -1.

Note: Use Dijkstra's algorithm or any other efficient shortest path algorithm to solve this problem.

inputFormat

The first line contains five space-separated integers: n m p1 p2 d, where n is the number of peaks, m is the number of paths, p1 is the starting peak, p2 is the destination peak, and d is the maximum allowed difficulty.

Each of the next m lines contains three integers x y t, indicating a bidirectional path between peaks x and y with a difficulty (and weight) of t.

outputFormat

Print a single integer representing the shortest total distance from peak p1 to peak p2 using only the paths whose difficulty is at most d. If no such path exists, print -1.

5 6 1 5 3
1 2 2
2 3 3
1 3 6
3 4 2
4 5 4
3 5 3

8