Maximum Flow and Minimum Cost

Given a directed graph with n nodes and m edges. Each edge is described by two endpoints, its capacity, and the cost per unit of flow along that edge. The graph may contain multiple edges between the same pair of nodes. Your task is to compute two values:

• The maximum flow from node 1 to node n.
• The minimum total cost needed to achieve that maximum flow.

The formulation in LaTeX is given below:

\( \text{Given } n \text{ nodes and } m \text{ edges, for each edge } (u,v) \text{ with capacity } c \text{ and cost } w, \text{ find the maximum flow from 1 to } n \text{ and the corresponding minimum total cost.} \)

inputFormat

The first line contains two integers n and m separated by a space, indicating the number of nodes and edges. Each of the following m lines contains four integers u v c w, which describe an edge from node u to node v with capacity c and cost per unit flow w.

outputFormat

Output two space-separated integers on a single line: the maximum flow from node 1 to node n and the minimum total cost to achieve that flow.

sample

3 3
1 2 3 1
1 3 2 2
2 3 2 3

4 12