#include<vector>
#include<deque>
#include<limits>
#include<algorithm>
#include<iostream>


struct CycleCancellingFlowNetwork {
    struct Arc {
        int start_;
        int end_;
        int flow_;
        int capacity_;
        int cost_;
        
        int get_dest(int from) {  // Return the destination node if we were to traverse the arc from node `from`
            if(from == start_) {
                return end_;
            } else {
                return start_;
            }
        }
        
        void add_flow(int from, int to_add) {  // Adds flow from originating vertex `from`
            if(from == start_) {
                flow_ += to_add;
            } else {
                flow_ -= to_add;
            }
        }
        
        int get_capacity(int from) {  // Gets the capacity of the edge if the originating vertex is `from`
            if(from == start_) {
                return capacity_ - flow_;
            } else {
                return flow_;
            }
        }
        
        int get_cost_from(int from) {
            if(from == start_) {
                return cost_;
            } else {
                return -cost_;
            }
        }
    };
    
    struct Node {
        int index_;
        std::vector<Arc*> connected_arcs_;
    };
    
    std::vector<Node> nodes_;
    std::deque<Arc> arcs_;
    
    void add_node() {
        nodes_.push_back({int(nodes_.size()), {}});
    }
    
    void add_arc(int start, int end, int flow, int capacity, int cost) {
        arcs_.push_back({start, end, flow, capacity, cost});
        nodes_[start].connected_arcs_.push_back(&arcs_.back());
        nodes_[end].connected_arcs_.push_back(&arcs_.back());
    }
    
    void cycle_cancel_min_flow() {
        struct State {
            int distance;
            Arc* arc_traversed;
        };
        
        while(1) {
            std::vector<std::vector<State> > state(1, std::vector<State>(nodes_.size(), {0, NULL}));
            
            // Perform the Bellman–Ford algorithm to find a negative cost cycle
            for(int level=0; level < (int)nodes_.size(); level++) {
                state.push_back(state[level]);  // Create next edge level
                for(int i=0; i < (int)nodes_.size(); i++) {
                    if(level == 0 || state[level][i].distance < state[level-1][i].distance) {  // Node is active?
                        for(Arc* arc : nodes_[i].connected_arcs_) {
                            if(arc->get_capacity(i) > 0) {
                                int next_distance = state[level][i].distance + arc->get_cost_from(i);
                                int next_i = arc->get_dest(i);
                                
                                if(next_distance < state[level+1][next_i].distance) {
                                    state[level+1][next_i].distance = next_distance;
                                    state[level+1][next_i].arc_traversed = arc;
                                }
                            }
                        }
                    }
                }
            }
            // Now identify the cycle
            bool valid = false;
            
            for(int i=0; i<(int)nodes_.size(); i++) {
                // See if this node ends in a path of length n+1 (and thus has to contain a cycle)
                if(state[(int)nodes_.size()-1][i].distance > state[(int)nodes_.size()][i].distance) {
                    std::vector<Arc*> path;  // The path we traversed to get to our cycle
                    std::vector<bool> explr((int)nodes_.size(), false);  // Nodes we have explored
                    int cur_i = i;  // Index of current node
                    int cur_level = (int)nodes_.size();  // Current level in the Belleman-Ford computed matrix
                    int capacity = std::numeric_limits<int>::max();  // Maximum capacity in the cycle
                    
                    valid = true;
                    
                    while(!explr[cur_i]) {
                        State cur_state = state[cur_level][cur_i];
                        
                        explr[cur_i] = true;
                        path.push_back(cur_state.arc_traversed);
                        cur_i = cur_state.arc_traversed->get_dest(cur_i);  // Traverse backwards
                        cur_level--;
                    }
                    int initial_i = cur_i;
                    
                    reverse(path.begin(), path.end());
                    for(int j=0; j == 0 || cur_i != initial_i; j++) {
                        capacity = std::min(capacity, path[j]->get_capacity(cur_i));
                        cur_i = path[j]->get_dest(cur_i);  // Traverse forward
                        
                        if(cur_i == initial_i) {
                            path.resize(j+1);  // Cut out part of the path that exceeds the cycle
                            break;
                        }
                    }
                    for(auto arc : path) {  // Push the flow through the cycle
                        arc->add_flow(cur_i, capacity);
                        cur_i = arc->get_dest(cur_i);
                    }
                    break;
                }
            }
            if(!valid) return;  // There are no longer any negative cycles
        }
    }
};


int main() {
    CycleCancellingFlowNetwork graph;
    
    for(int i=0; i<6; i++) graph.add_node();  // Initialize 6 nodes
    // Add edges of our graph
    graph.add_arc(0, 1, 4, 4, 1);
    graph.add_arc(0, 3, 2, 2, 5);
    graph.add_arc(1, 2, 2, 2, 1);
    graph.add_arc(1, 3, 2, 6, 1);
    graph.add_arc(2, 1, 0, 2, 0);
    graph.add_arc(2, 5, 2, 4, 0);
    graph.add_arc(3, 4, 4, 8, 1);
    graph.add_arc(4, 2, 0, 6, -3);
    graph.add_arc(4, 5, 4, 4, 1);
    
    graph.cycle_cancel_min_flow();  // Do the cycle cancelling
    
    int result = 0;
    for(auto& arc : graph.arcs_) {  // Calculate the cost of our flow
        result += arc.cost_ * arc.flow_;
    }
    std::cout << result << '\n';
    
    return 0;
}