Optimal flow of magnitude 1#4582
Given a directed graph with vertices and edges, where vertex is the source and vertex is the sink, each edge has an associated cost.
Your task is to determine the optimal flow of magnitude through this network, meaning a flow of magnitude that incurs the minimum cost. Although edge costs can be negative, the graph is guaranteed to have no negative weight cycles. While capacities are not specified, it is known that they are at least .
The first line contains two integers and (2 \leq n \leq 1000, 0 \leq m \leq 10000). The next lines each contain three integers , , and , indicating an edge from vertex to vertex with a cost of (1 \leq x, y \leq n, -1000 \leq p \leq 1000). The graph may include loops and multiple edges.
Output a single integer representing the cost of the optimal flow of magnitude . If it is not possible to achieve a flow of magnitude in the network, output NO.
Example 1