Shortest Path in a Weighted Graph

You are given a network of warehouses. The warehouses are connected by bidirectional roads with positive integer lengths. Your task is to compute the shortest distance between two specified warehouses using Dijkstra's algorithm.

The problem is formalized as follows:

Given a weighted graph \(G(V,E)\) where each edge \((u,v)\) has an associated positive weight \(d_{uv}\), determine the minimum distance from a starting warehouse \(s\) to a target warehouse \(t\). If no path exists, return -1.

inputFormat

The input is read from standard input and adheres to the following format:

n m
u1 v1 d1
u2 v2 d2
... 
um vm dm
s t

Where:

• \(n\) is the number of warehouses (nodes).
• \(m\) is the number of roads.
• Each of the next \(m\) lines contains three integers \(u\), \(v\) and \(d\), representing a road between warehouses \(u\) and \(v\) with length \(d\).
• The last line contains two integers \(s\) (the start) and \(t\) (the target).

outputFormat

Output a single integer to standard output representing the shortest distance from the starting warehouse \(s\) to the target warehouse \(t\). If there is no valid path, output -1.

4 4
1 2 4
2 3 2
3 4 7
1 3 3
1 4

10