Minimum Transit Time in Shipment Network

We are given a directed graph with n nodes and m shipments. Each shipment is represented as a tuple \((u, v, t)\) where u is the starting node, v is the destination node, and t is the transit time. When multiple shipments exist between the same pair of nodes, only the one with the minimum transit time is considered.

The problem can be formalized as follows:

Let \(G = (V, E)\) be a directed graph where \(V = \{1, 2, \ldots, n\}\) and each edge \((u, v)\) has a weight \(w(u,v)\) defined as: \[ w(u,v)=\min\{t: (u,v,t)\text{ is a shipment}\}\]

Your task is to compute the minimum transit time required to travel from node x to node y by considering only the minimum shipment between any two nodes. If x equals y, the answer should be 0. If there is no valid route from x to y, output -1.

inputFormat

The input is provided via standard input (stdin) and has the following format:

n m
u1 v1 t1
u2 v2 t2
... (m shipments)
x y

The first line contains two integers n and m. Each of the next m lines contains three integers: u, v, and t, representing a shipment from node u to node v with transit time t. The last line contains two integers, x and y, which are the starting and destination nodes, respectively.

outputFormat

Output a single integer representing the minimum transit time from node x to node y using the best shipments. If there is no path from x to y, output -1.

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

12