Fast Maximum Flow

Given a graph with N (2 <= N <= 10,000) vertices numbered 1 to N and M (1 <=
M <= 50,000) undirected, weighted edges, compute the maximum flow from vertex 1
to vertex N.

PROBLEM NAME: fastflow

INPUT FORMAT:

* Line 1: Two space-separated integers, N and M.

* Lines 2..M+1: Each line contains three integers A, B, and C,
        denoting that there is an edge of capacity C (1 <= C <=
        1,000,000,000) between nodes A and B (1 <= A, B <= N). Note
        that it is possible for there to be duplicate edges, as well
        as an edge from a node to itself.

SAMPLE INPUT:

4 6
1 2 3
2 3 4
3 1 2
2 2 5
3 4 3
4 3 3

OUTPUT FORMAT:

* Line 1: Print a single integer (which may not fit into a 32-bit
        integer) denoting the maximum flow between 1 and N.

SAMPLE OUTPUT:

5

OUTPUT DETAILS:

Viewing the problem as max-flow, we may send 3 units of flow through the
path 1 - 2 - 3 - 4 and 2 units of flow through the path 1 - 3 - 4. Viewing
the problem as min-cut, we may cut the first and third edges. Either way
the total is 5.