#include <bits/stdc++.h>
using namespace std;
#define VI vector<int>
#define PII pair<int, int>
#define ll long long

class Graph {
    public: 
    
    Graph(int n) {
        _N = n;
        _G = vector<VI> (n, vector<int> ());
        _cap = vector<VI> (n, vector<int> (n, 0));
        _cost = vector<VI> (n, vector<int> (n, 0));
    }

    void setSource(int source) {
        _source = source;
    }

    void setDest(int dest) {
        _dest = dest;
    }

    void addEdge(int x, int y, int cap, int cost = 0) {
        if(_cap[x][y]) {
            _cap[x][y] += cap;
            return;
        }
        _G[x].push_back(y);
        _G[y].push_back(x);
        _cap[x][y] = cap;
        _cost[x][y] = cost;
    }

    bool augmentingPath(vector<ll> &d, vector<int> &dad) {
        queue<int> Q;
        Q.push(_source);
        d[_source] = 0;
        dad[_source] = _source;

        while(!Q.empty()) {
            int node = Q.front();
            Q.pop();
            
            for(auto temp : _G[node]) {
                if(_cap[node][temp] <= 0)
                    continue;
                if(d[temp] > d[node] + _cost[node][temp]) {
                    dad[temp] = node;
                    d[temp] = d[node] + _cost[node][temp];
                    Q.push(temp);
                }
            }
        }

        return (dad[_dest] != -1);
    }

    pair<int, ll> minCostMaxFlow() {
        vector<int> dad(_N, -1);
        vector<ll> d(_N, _COST_INF);
        
        int flow = 0;
        ll flowcost = 0;

        while(augmentingPath(d, dad)) {
            int f = _CAP_INF;
            for(int node = _dest; node != _source; node = dad[node]) 
                f = min(f, _cap[dad[node]][node]);
            for(int node = _dest; node != _source; node = dad[node]) {
                _cap[dad[node]][node] -= f;
                _cap[node][dad[node]] += f;
            }
            flow += f;
            flowcost += d[_dest];
            dad = vector<int> (_N, -1);
            d = vector<ll> (_N, _COST_INF);
        }
        
        return make_pair(flow, flowcost);
    }
    
    int _N;
    vector<VI> _G;
    vector<VI> _cap;
    vector<VI> _cost;
    int _source, _dest;
    static const int _CAP_INF = (1 << 30);
    static const ll _COST_INF = (1LL << 60);
};


int main() {
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");

    int n, m; cin >> n >> m;

    Graph G(n);

    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        a--, b--;
        G.addEdge(a, b, c);
    }

    G.setSource(0);
    G.setDest(n - 1);
    
    int f = G.minCostMaxFlow().first;
    cout << f << "\n";
}