Shortest Path in a Directed Network

You are given a directed network with \(n\) nodes (computers) and \(m\) weighted edges. Each edge from node \(u\) to node \(v\) has a weight \(d\) that represents the time required for data to travel from \(u\) to \(v\). Your task is to determine the minimum amount of time required to travel from a starting node \(s\) to a target node \(t\). If there is no path from \(s\) to \(t\), output -1.

The total cost of a path is defined as the sum of the weights of the edges in the path, i.e., \(\text{cost} = \sum_{i=1}^{k} d_i\), where \(k\) is the number of edges in the path.

inputFormat

The first line contains two integers (n) and (m) which denote the number of nodes and the number of edges, respectively. This is followed by (m) lines, each containing three integers (u), (v), and (d) representing a directed edge from node (u) to node (v) with weight (d). The last line contains two integers (s) and (t) denoting the starting and target nodes.

outputFormat

Output a single integer — the minimum travel time from node (s) to node (t). If there is no path between (s) and (t), output -1.## sample

5 6
1 2 2
2 3 3
3 5 1
4 3 4
1 4 8
5 4 2
1 5

6