//#include <bits/stdc++.h>
#include "/usr/local/include/bits/stdc++.h"


using namespace std;

const int MAX = 1e6;
#define  ll long long
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

//vector <vector<int>> capacitate;
//
//int path[MAX];
//bool vizitat[MAX];
//
//int M, N;
//ll pathLength;

/// ======================== Bellmanford  O(V * E^2)
/// https://www.youtube.com/watch?v=LdOnanfc5TM&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=33
// DFS, BFS, DIJKSTRA
//int getPath(int startNode, int targetNode, int curLen, int maxCap) {
//    path[curLen] = startNode;
//
//    if (startNode == targetNode) {
//        pathLength = curLen + 1;
//        return maxCap;
//    }
//
//    int res = 0;
//    vizitat[startNode] = true;
//
//    for (int i = 0; i < N; ++i) {
//        if (vizitat[i] || capacitate[startNode][i] <= 0) continue;
//        res = getPath(i, targetNode, curLen + 1, min(maxCap, capacitate[startNode][i]));
//        if (res > 0) break;
//    }
//
//    return res;
//}
//
//ll maxFlow(int startNode, int endNode) {
//    ll totalFlow = 0;
//
//    while (true) {
//        memset(vizitat, false, sizeof (vizitat));
//        int newFlow = getPath(startNode, endNode, 0, INT_MAX);
//
//        if (newFlow <= 0)break; // once there is no paths anymore stop the algo
//
//        for (int i = 1; i < pathLength; ++i) {
//            int m = path[i - 1];
//            int n = path[i];
//            capacitate[m][n] -= newFlow;
//            capacitate[n][m] += newFlow;
//        }
//        totalFlow += newFlow;
//    }
//
//    return totalFlow;
//}


/// ======================== Capacity Scaling   O(E^2 * Log(U)) or O(E * V Log(U)) if SHORTEST PATH
// U = MAX Value ( Capacities)
// delta = smallest power of 2 less than or equal to U.
// https://www.youtube.com/watch?v=1ewLrXUz4kk&list=PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P&index=40
// repeatedly delta = delta / 2
vector <vector<int>> capacity;

vector<bool> visited;
vector<int> parent;
int remainingCapacity = 0;
int delta;
int M, N;

ll dfs(int s, int t, int flow) {


    if (s == t) return flow;

    visited[s] = true;
    for (int i = 0; i < capacity[s].size(); ++i) {
        int cap = capacity[s][i];
        if (cap >= delta && !visited[i]) {
            parent[i] = s;
            ll bottleNeck = dfs(i, t, min(cap, flow));
            if (bottleNeck > 0) {
                return bottleNeck;
            }
        }

    }


    return 0;
}

ll maxFlow(int s, int t) {
    delta = (long) pow(2, (int) floor(log(delta) / log(2)));

    ll flow = 0;
    parent[s] = -1;
    for (ll newFlow = 0; delta > 0; delta /= 2) {
        do {
            fill(visited.begin(), visited.end(), false);
            newFlow = dfs(s, t, MAX * 1000);

            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                capacity[u][v] -= newFlow;
                capacity[v][u] += newFlow;
            }
            flow += newFlow;
        } while (newFlow != 0);
    }

    return flow;
}

//4 5
//1 2 3
//1 3 5
//2 4 6
//3 4 4
//3 2 3
int main() {

    fin >> N >> M;
    visited.resize(N + 10, false);
    parent.resize(N + 10, 0);

    capacity.resize(N + 10, vector<int>(N + 10,0));

    for (int i = 0; i < M; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        capacity[x][y] = z;
        delta = max(delta, z);
    }
    fout << maxFlow(1, N);

//
//    cin >> N >> M;
//    visited.resize(N + 10, false);
//    parent.resize(N + 10, 0);
//
//    capacity.resize(N + 10, vector<int>(N + 10,0));
//
//    for (int i = 0; i < M; ++i) {
//        int x, y, z;
//        cin >> x >> y >> z;
//        capacity[x][y] = z;
//        delta = max(delta, z);
//    }
//    cout << maxFlow(1, N);


    return 0;
}