Shortest Path in a Weighted Graph

You are given an undirected weighted graph representing intersections and roads. The graph has N intersections, numbered from 0 to N-1, and M bidirectional roads. Each road connects two intersections and has an associated travel time. Given two intersections A and B, your task is to find the minimum total travel time from A to B using the available roads. If there is no possible route from A to B, output -1.

The problem can be formally described as: Given a graph \(G=(V,E)\) with vertices \(V = \{0, 1, \ldots, N-1\}\) and edges \(E\) where each edge \((u,v)\) has a weight \(w\), find the shortest path from vertex \(A\) to vertex \(B\). This is a classical single-source shortest path problem, which can be solved using Dijkstra's algorithm.

Note: All input is provided through standard input (stdin) and all output should be printed to standard output (stdout).

inputFormat

The first line contains three integers \(N\), \(A\), and \(B\) separated by spaces:

• \(N\): the number of intersections.
• \(A\): the starting intersection.
• \(B\): the destination intersection.

The second line contains an integer \(M\), the number of roads.

Each of the following \(M\) lines contains three integers \(u\), \(v\), and \(w\) separated by spaces, representing a road between intersections \(u\) and \(v\) with travel time \(w\).

outputFormat

Output a single integer: the minimum travel time needed to travel from intersection \(A\) to \(B\). If no such route exists, output -1.

5 0 4
5
0 1 10
1 2 5
2 3 2
0 3 20
2 4 1

16