Minimum Time to Travel

You are given a directed weighted graph with \(N\) nodes and \(M\) edges. Each edge is represented by a tuple \((u, v, w)\) which indicates that there is a directed edge from node \(u\) to node \(v\) with travel time \(w\).

The input is provided as follows:

• \(N\): Number of nodes.
• \(M\): Number of edges.
• The next \(M\) lines: Each line contains three integers \(u\), \(v\), and \(w\) representing a directed edge from node \(u\) to node \(v\) with travel time \(w\).
• The last line contains two integers \(S\) and \(D\) which are the source and destination nodes respectively.

Your task is to compute the minimum travel time from \(S\) to \(D\) using an efficient algorithm such as Dijkstra's algorithm. If there is no valid path from \(S\) to \(D\), output \(-1\).

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers \(N\) and \(M\).
• The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\) representing a directed edge from node \(u\) to node \(v\) with weight \(w\).
• The last line contains two integers \(S\) and \(D\), representing the source and destination nodes respectively.

outputFormat

Output to stdout a single integer representing the minimum travel time from \(S\) to \(D\). If no such path exists, output \(-1\).

5 6
1 2 2
1 3 4
2 4 7
3 4 1
4 5 3
3 5 6
1 5

8