Minimum Travel Time

You are given a directed graph with \(N\) nodes and \(M\) weighted edges. Each edge is represented by three integers \(u\), \(v\), and \(w\), indicating an edge from node \(u\) to node \(v\) with a weight (or travel time) of \(w\). Your task is to determine the minimum time required to travel from node 1 to node \(N\). If there is no available route from node 1 to node \(N\), output -1.

Note: The weights can be viewed as travel times, and the graph may contain multiple edges and paths. Use an efficient shortest path algorithm (such as Dijkstra's algorithm) to handle large inputs.

inputFormat

The first line contains two integers \(N\) and \(M\) separated by a space, representing the number of nodes and edges, respectively.

The following \(M\) lines each contain three space-separated integers \(u\), \(v\), and \(w\), which describe an edge from node \(u\) to node \(v\) with weight \(w\).

outputFormat

Output a single integer, which is the minimum travel time from node 1 to node \(N\). If there is no path connecting node 1 to node \(N\), output -1.

5 6
1 2 5
2 3 10
1 3 15
3 4 7
2 5 9
4 5 3

14