Optimal flow of magnitude 1
Given a directed graph with n vertices and m edges, where vertex 1 is the source and vertex n is the sink, each edge has an associated cost.
Your task is to determine the optimal flow of magnitude 1 through this network, meaning a flow of magnitude 1 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 1.
Input
The first line contains two integers, n and m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000). The next m lines each contain three integers x, y, and p, indicating an edge from vertex x to vertex y with a cost of p (1 ≤ x, y ≤ n, -1000 ≤ p ≤ 1000). The graph may include loops and multiple edges.
Output
Output a single integer representing the cost of the optimal flow of magnitude 1. If it is not possible to achieve a flow of magnitude 1 in the network, output NO.