#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>

#define DEFAULT_INPUT "maxflow.in"
#define DEFAULT_OUTPUT "maxflow.out"
#define MAX_N 110010
#define RELABEL_DONE {0, 0, 0}

struct edge_data {
    int c;
    int f;
};

struct edge {
    int x, y;
    // we can chane this to int
    edge_data *data;
};

void push_to_edge(int x, edge e, int excess[]) {
    edge_data *data = e.data;

    if (e.x == x) {
        if (excess[x] > data->c - data->f) {
            // a saturating push
            excess[x] -= data->c - data->f;
            excess[e.y] += data->c - data->f;
            data->f = data->c;
        } else {
            // a non-saturating push
            data->f += excess[x];
            excess[e.y] += excess[x];
            excess[x] = 0;
        }
    } else {
        if (excess[x] > data->f) {
            // a saturating reverse push
            excess[x] -= data->f;
            excess[e.x] += data->f;
            data->f = 0;
        } else {
            // a non-saturating reverse push
            data->f -= excess[x];
            excess[e.x] += excess[x];
            excess[x] = 0;
        }
    }
}

edge relabel(int x, std::vector<edge> adj[], int labels[]) {
    int min_val = 0x7fffffff;

    for (auto e: adj[x]) {
        if (e.x == x) {
            if (e.data->c <= e.data->f) {
                continue;
            }
            if (labels[x] > labels[e.y]) {
                return e;
            }
            if (labels[e.y] < min_val) {
                min_val = labels[e.y];
            }
        } else {
            if (e.data->f <= 0) {
                continue;
            }
            if (labels[x] > labels[e.x]) {
                return e;
            }
            if (labels[e.x] < min_val) {
                min_val = labels[e.x];
            }
        }
    }

    labels[x] = min_val + 1;

    return RELABEL_DONE;
}

void init(std::vector<edge> adj[], int labels[], 
        std::queue<int> &active_vertices, 
        int excess[], 
        int n,
        int &s,
        int &t) {
    
    int is_source, is_sink;

    // suppose there are only one source and one sink
    for (int i = 1; i <= n; i++) {
        is_source = 1;
        is_sink = 1;
        for (auto e: adj[i]) {
            if (e.y == i) {
                is_source = 0;
            } else {
                is_sink = 0;
            }
        }
        if (is_source) {
            s = i;
        }
        else if (is_sink) {
            t = i;
        }
    }

    memset(labels + 1, 0, sizeof(int) * n);
    memset(excess + 1, 0, sizeof(int) * n);
    labels[s] = n;

    for (auto e: adj[s]) {
        e.data->f = e.data->c;
        excess[e.y] = e.data->c;
        active_vertices.push(e.y);
    }
}

void print_info(/*std::vector<edge> adj[], */int labels[], int excess[], int n) {
    for (int i = 1; i <= n; i++) {
        std::cout << labels[i] << ' ';
    }
    std::cout << '\n';
    
    for (int i = 1; i <= n; i++) {
        std::cout << excess[i] << ' ';
    }
    std::cout << "\n\n";

    std::cout.flush();
}

int discharge(std::vector<edge> adj[], int n) {
    std::queue<int> active_vertices;
    int labels[MAX_N], excess[MAX_N];
    int x;
    edge e;
    int s, t;

    init(adj, labels, active_vertices, excess, n, s, t);

    while (!active_vertices.empty()) {
        //print_info(labels, excess, n);
        
        x = active_vertices.front();
        active_vertices.pop();

        if (!excess[x]) {
            continue;
        }

        e = relabel(x, adj, labels);

        if (labels[x] > n) {
            continue;
        }

        if (e.x != 0) {
            push_to_edge(x, e, excess);
        
            int y = (e.x == x ? e.y : e.x), y_excess = excess[y];
            
            // we can change the order of these two
            if (y_excess && excess[y] && y != t && y != s) {
                active_vertices.push(y);
            }
            if (excess[x]) {
                active_vertices.push(x);
            }
        } else {
            // not sure
            active_vertices.push(x);
        }
    }

    return excess[t];
}

int main(int argc, char *argv[]) {
    std::ifstream fin;
    std::ofstream fout;
    
    if (argc == 1) {
        fin.open(DEFAULT_INPUT);
    } else {
        fin.open(argv[1]);
    }

    int n, m, x, y, c;
    std::vector<edge> adj[MAX_N];

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> c;
        edge_data *data = new edge_data[1];
        data->c = c;
        data->f = 0;
        // I should actually store pointers here
        adj[x].push_back({x, y, data});
        adj[y].push_back({x, y, data});
    }

    fin.close();

    return 0;

    int max_flow = discharge(adj, n);

    if (argc < 3) {
        fout.open(DEFAULT_OUTPUT);
    } else {
        fout.open(argv[2]);
    }

    fout << max_flow << '\n';

    fout.close();
}