Minimal Edge Capacity for Maximum Flow Reduction

In a water supply network represented by a directed graph, you are given n nodes and m edges. Each edge from node u to node v has a capacity c (a positive integer). The maximum water flow from the main reservoir at node 1 to the most remote village at node n is determined using the Edmonds-Karp algorithm.

Your task is to identify an edge whose removal (i.e. subtracting its full capacity from the edge) causes a positive reduction in the overall maximum flow. Among all such edges, return the minimal capacity c. In other words, if the original maximum flow is \(F\) and the new maximum flow after removing an edge is \(F'\), then if \(F - F' > 0\) the removal is effective. You should output \(\min\{ c \mid F - F' > 0 \}\); if no edge removal yields a flow reduction or if there is no flow from 1 to \(n\) initially, output \(-1\).

Note: Any formulas should appear in LaTeX format. For example, the reduction condition is given by \(F - F' > 0\) and the answer is \(\min\{ c \mid F - F' > 0 \}\).

inputFormat

The first line contains two integers (n) and (m), representing the number of nodes and edges, respectively. This is followed by (m) lines, each containing three integers (u), (v), and (c), which specify a directed edge from node (u) to node (v) with capacity (c).

outputFormat

Output a single integer: the minimal capacity of an edge whose removal causes a positive reduction in the maximum water flow from node 1 to node (n). If no such edge exists, output (-1).## sample

4 5
1 2 10
2 3 5
2 4 15
3 4 10
4 3 10

5