Shortest Path in a Weighted Graph

Given a weighted undirected graph representing cities connected by roads, your task is to find the shortest travel time from city 1 to city n using Dijkstra's algorithm. Each road is bidirectional and associated with a travel time.

If there is no valid path from city 1 to city n, output \(-1\).

The problem can be mathematically stated as follows: let \(G=(V,E)\) be an undirected graph with \(|V| = n\) and \(|E| = m\), where each edge \(e\) has a weight \(w_e\). Find the minimum travel time from vertex 1 to vertex n.

inputFormat

The first line contains two integers (n) and (m), representing the number of cities and roads respectively. Each of the following (m) lines contains three integers (u), (v), and (t) which indicate there is a bidirectional road connecting city (u) and city (v) with travel time (t).

outputFormat

Output a single integer representing the shortest travel time from city 1 to city n. If no path exists, output (-1).## sample

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

6