#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("maxflow.in");
ofstream cout("maxflow.out");
const int NMAX = 1000;
const int MMAX = 5000;
const int INF = 1e8;
struct maxFlow{
    int cap[2 * MMAX + 5];
    int cntEdges = 0;
    vector<pair<int, int>> v[NMAX + 5];
    int n;
    int s, t;
    void getGraphInfo(int x, int ss, int tt)
    {
        n = x;
        s = ss;
        t = tt;
    }
    void add_edge(int x, int y, int c)
    {
        cap[++cntEdges] = c;
        v[x].push_back({y, cntEdges});
        cap[++cntEdges] = 0;
        v[y].push_back({x, cntEdges});
    }
    vector<pair<int, int>> g[NMAX + 5];
    void clearG()
    {
        for(int i = 1; i <= n; i++)
            g[i].clear();
    }
    int dist[NMAX + 5];
    bool getLayeredNetwork()
    {
        queue<int> q;
        q.push(s);
        for(int i = 1; i <= n; i++)
            dist[i] = 0;
        dist[s] = 1;
        bool reachT = 0;
        while(!q.empty())
        {
            int nod = q.front();
            q.pop();
            if(nod == t)
                reachT = 1;
            for(pair<int, int>& it : v[nod])
            {
                if(cap[it.second])
                {
                    if(dist[it.first] == 0)
                        {dist[it.first] = dist[nod] + 1; q.push(it.first); g[nod].push_back(it);}
                    if(dist[it.first] == dist[nod] + 1)
                        {g[nod].push_back(it);}
                }
            }
        }
        return reachT;
    }
    int ind[NMAX + 5];
    int maxFlow = 0;
    int getOther(int x)
    {
        if(x & 1) return (x + 1);
        else return (x - 1);
    }
    int dfs(int nod, int mini)
    {
        if(nod == t)
        {
            maxFlow += mini;
            return mini;
        }
        int pushed = 0;
        while(mini > 0 && ind[nod] < (int) g[nod].size())
        {
            if(cap[g[nod][ind[nod]].second])
            {
                int val = dfs(g[nod][ind[nod]].first, min(mini, cap[g[nod][ind[nod]].second]));
                cap[g[nod][ind[nod]].second] -= val;
                cap[getOther(g[nod][ind[nod]].second)] += val;
                pushed += val;
                mini -= val;
            }
            ind[nod]++;
        }
        return pushed;
    }
    void getBlockingFlow()
    {
        for(int i = 1; i <= n; i++)
            ind[i] = 0;
        dfs(s, INF);
    }
    int dinic()
    {
        while(getLayeredNetwork())
        {
            getBlockingFlow();
            clearG();
        }
        return maxFlow; 
    }
};
int n, m;
maxFlow flow;
void readInput()
{
    cin >> n >> m;
    flow.getGraphInfo(n, 1, n);
    int x, y, z;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> z;
        flow.add_edge(x, y, z);
    }
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    cout << flow.dinic();
    return 0;
}