#include <bits/stdc++.h>

using namespace std;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

struct Graf
{
    vector<vector<int> > G, cap;
    vector<int> dad;
    int n;
    const int INF = (1 << 30);
    Graf (const int& __n) : n(__n), G(__n + 1), cap(__n + 1), dad(n + 1)
    {
        cap = vector<vector<int> > (n + 1, vector<int>(n + 1));
    }

    inline void AddEdge(int x, int y, int c)
    {
        G[x].emplace_back(y);
        G[y].emplace_back(x);
        cap[x][y] = c;
    }

    inline bool BFS()
    {
        queue<int> q;
        q.push(1);
        fill(dad.begin(), dad.end(), 0);
        dad[1] = 1;
        while(!q.empty())
        {
            auto x = q.front();
            q.pop();

            if(x == n)
                continue;

            for(auto y: G[x])
                if(!dad[y] && cap[x][y])
                {
                    dad[y] = x;
                    q.push(y);
                }
        }
        return dad[n];
    }

    inline int MaxFlow(){
        int x, flow, flowmax(0);
        while(BFS()){
            for(auto nod: G[n]){
                if(dad[nod] && cap[nod][n]){
                    dad[n] = nod;
                    flow = INF;
                    x = n;
                    while(x != 1){
                        flow = min(flow, cap[dad[x]][x]);
                        x = dad[x];
                    }

                    if(flow == INF)
                        continue;

                    x = n;
                    while(x != 1){
                        cap[dad[x]][x] -= flow;
                        cap[x][dad[x]] += flow;
                        x = dad[x];
                    }
                    flowmax += flow;
                }
            }
        }
        return flowmax;
    }
};

int main()
{
    BUNA("maxflow");
    int n, m;
    cin >> n >> m;

    Graf g(n);
    for(int i = 1; i <= m; ++i){
        int x, y, c;
        cin >> x >> y >> c;

        g.AddEdge(x, y, c);
    }

    cout << g.MaxFlow() << '\n';
    PA();
}