Shortest Path in a Directed Graph

You are given a weighted directed graph with (N) nodes and (M) edges. Each edge is represented by a tuple ((u, v, w)) indicating a directed edge from node (u) to node (v) with travel time (w). You are also given a starting node and a target node. Your task is to compute the shortest travel time from the starting node to the target node. If there is no path from the start to the target, output -1.

Note: The input graph may be a Directed Acyclic Graph (DAG) or may contain cycles. When a valid path does not exist, your program should output -1.

The problem can be formulated as follows:

Given integers (N) and (M), a start node (s) and a target node (t), and a list of (M) edges ((u, v, w)), find the minimum total weight (travel time) to reach (t) from (s), or report (-1) if no such path exists.

inputFormat

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

N M
s t
u1 v1 w1
u2 v2 w2
... 
uM vM wM

Where:

• \(N\) is the number of nodes (numbered from 1 to \(N\)).
• \(M\) is the number of edges.
• \(s\) is the starting node and \(t\) is the target node.
• Each of the next \(M\) lines contains three integers \(u, v, w\), representing an edge from node \(u\) to node \(v\) with weight \(w\).

outputFormat

Output a single integer to standard output (stdout): the shortest travel time from node \(s\) to node \(t\). If there is no valid path between \(s\) and \(t\), output \(-1\).

## sample

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

6