Maximum flow of minimum cost#5447
Given a directed graph where each edge has a capacity and a cost, find the maximum flow with the minimum cost from vertex 1 to vertex n.
The first line contains two integers and — the number of vertices and the number of edges in the graph (2 \leq n \leq 100, 1 \leq m \leq 1000). Each of the following lines contains four integers: the endpoints of the corresponding edge, its capacity, and its cost. Both capacities and costs do not exceed 10^5.
Print a single integer — the cost of the maximum flow with the minimum cost from vertex 1 to vertex n. The answer does not exceed 2^{63}-1. It is guaranteed that the graph does not contain any cycles with negative cost.
Example 1