Shortest Path in a Road Network

You are given a network of cities connected by bidirectional roads. Each road has a positive length. Your task is to compute the shortest distance from a specified start city to a destination city using Dijkstra's algorithm.

Given a weighted graph \(G=(V,E)\) where each edge \(e\) has a weight \(w(e)\), the shortest distance between two vertices \(u\) and \(v\) is defined as \(d(u,v)=\min \sum_{e\in path} w(e)\). If there is no path from the start city to the destination city, output \(-1\). If the start and destination are the same, the distance is \(0\).

inputFormat

The input is read from the standard input with the following format:

<n> <m>
 a1 b1 w1
 a2 b2 w2
 ...
 am bm wm
<start> <destination>

Where:

• n is the number of cities.
• m is the number of roads.
• Each of the next m lines contains three integers a, b, and w, representing a bidirectional road between cities a and b with length w.
• The last line contains two integers: start and destination, indicating the starting city and the destination city respectively.

outputFormat

Output the shortest distance from the start city to the destination city. If no path exists, output \(-1\).

## sample

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

3

</p>