Shortest Path in a Directed Graph

You are given a directed graph with n nodes and m edges. Each edge has a positive travel time. Your task is to compute the minimum travel time required to move from a given start node to a target node. If the target node is unreachable from the start node, output -1.

The graph is represented by m edges. Each edge is described by three integers \( u, v, w \), where \( u \) is the source node, \( v \) is the destination node, and \( w \) is the travel time from \( u \) to \( v \).

Formally, given a graph \( G = (V, E) \) where \( V = \{1, 2, \dots, n\} \) and \( E = \{(u, v, w)\} \), find the shortest travel time from start to target. If no path exists, return -1.

inputFormat

The input is given from standard input (stdin) in the following format:

n
m
u1 v1 w1
u2 v2 w2
... 
um vm wm
start target

Here, the first line contains an integer \( n \) denoting the number of nodes. The second line contains an integer \( m \) denoting the number of edges. The next \( m \) lines each contain three integers \( u, v, w \) describing an edge from node \( u \) to node \( v \) with travel time \( w \). The last line contains two integers, the start node and the target node.

outputFormat

Output the minimum travel time from the start node to the target node. If the target node is unreachable, output -1. The answer should be printed to standard output (stdout).

5
5
1 2 2
2 3 4
1 3 1
3 4 3
4 5 1
1 5

5