#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

bool BFS(int** G, int V, int s, int d, int* parent);

int Ford_Fulkerson(int** G, int& V, int s, int d) {
    int u, v;
    int** rG; // graf rezidual 
    rG = new int* [V + 1];
    for (int i = 1; i <= V; i++) {
        rG[i] = new int[V + 1];
    }
    for (u = 1; u <= V; u++)
        for (v = 1; v <= V; v++)
            rG[u][v] = G[u][v];
    //
    int* parent = new int[V + 1];
    int max_flow = 0;
    while (BFS(rG, V, s, d, parent)) {
        int path_flow = INT_MAX;
        for (v = d; v != s; v = parent[v])
        {
            u = parent[v];
            path_flow = min(path_flow, rG[u][v]);
        }
        for (v = d; v != s; v = parent[v])
        {
            u = parent[v];
            rG[u][v] -= path_flow;
            rG[v][u] += path_flow;
        }

        max_flow += path_flow;
    }
    delete[] rG;
    return max_flow;
}

bool BFS(int** G, int V, int s, int d, int* parent) {

    bool* viz = new bool[V + 1];
    for (int i = 1; i <= V; i++)
        viz[i] = false;
    queue<int> Q;
    Q.push(s);
    parent[s] = -1;
    viz[s] = true;
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int v = 1; v <= V; v++) {
            if (viz[v] == false && G[u][v] > 0)
            {
                Q.push(v);
                parent[v] = u;
                viz[v] = true;
            }
        }
    }
    if (viz[d] == true) {
        delete[] viz;
        return true;
    }
    delete[] viz;
    return false;

}

int main() {
    int n, m, i, j, x, y, z;
    fin >> n >> m;
    int** G = new int* [n+1];
    for (i = 1; i <= n; i++) {
        G[i] = new int[n+1];
        for (j = 1; j <= n; j++) {
            G[i][j] = 0;
        }
    }
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        G[x][y] = z;
    }
    cout << "da";
    fout << Ford_Fulkerson(G, n, 1, n);
    delete[] G;
}