Shortest Path in a Highway Network

Given a network of cities connected by highways, each highway has a length. You are provided with the number of cities (n), the number of highways (m), and details of each highway connecting two cities with a weight (w). You are also given two cities: a start city and an end city. Your task is to compute the length of the shortest path from the start city to the end city using Dijkstra's algorithm. If there is no valid path, output (-1).

The input data follows the following format: the first line contains two integers (n) and (m). The second line contains two integers denoting the start and end cities. This is followed by (m) lines each containing three integers (u), (v), and (w) representing a highway between cities (u) and (v) with length (w).

inputFormat

The first line contains two integers (n) and (m) separated by a space.\nThe second line contains two integers: (start) and (end).\nEach of the next (m) lines contains three integers (u), (v), and (w) separated by spaces, representing a highway connecting cities (u) and (v) with length (w).

outputFormat

Output a single integer: the length of the shortest path from the start city to the end city. If no such path exists, output (-1).## sample

4 4
1 4
1 2 10
2 3 10
3 4 10
1 4 50

30