// O(V^2 * E)

#include <fstream>
#include <vector>
#include <queue>

#define MAXN 1001

using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");

int V, E;
vector <int> Gf[MAXN];
int c[MAXN][MAXN];
int s,t;
int f1[MAXN][MAXN];
bool used[MAXN];
int father[MAXN];
vector <int> levGf[MAXN];

inline void readAndBuild() {
    in >> V >> E;
    s = 1;
    t = V;
    
    int x, y, z;
    for (int e = 0; e < E; ++ e) {
        in >> x >> y >> z;
        
        if (c[y][x] == 0) {
            Gf[x].push_back(y);
            c[x][y] = z;
            
            Gf[y].push_back(x);
        } else {
            c[x][y] = z;
        }
    }
}

// builds the level graph of Gf
inline bool bfs() {
    queue <int> q;
    q.push(s);
    
    for (int i = 1; i <= V; ++ i) {
        used[i] = false;
    }
    
    for (int node = q.front(); !q.empty(); node = q.front()) {
        q.pop();
        
        if (node == t) {
            return true;
        }
        
        for (vector <int>::iterator it = Gf[node].begin(); it != Gf[node].end(); ++ it) {
            if (!used[*it] && f1[node][*it] < c[node][*it]) {
                used[*it] = true;
                levGf[node].push_back(*it);
                q.push(*it);
            }
        }
    }
    
    return false;
}

// find a blocking flow in the level graph
inline bool dfs(int node) {
    if (node == t) return true;
    
    bool foundBlockingFlow = false;
    
    for (vector <int>::iterator it = levGf[node].begin(); it != levGf[node].end(); ++ it) {
        if (father[*it] == -1 && f1[node][*it] < c[node][*it]) {
            father[*it] = node;
            foundBlockingFlow = dfs(*it);
            
            if (foundBlockingFlow) return true;
        }
    }
    
    return false;
}

inline int maxFlowDinic() {
    int maxFlow = 0;
    
    // build the level graph and check if an augmentation path exists
    for (bool sinkReached = bfs(); sinkReached; sinkReached = bfs()) {
        for (int i = 1; i <= V; ++ i) {
            father[i] = -1;
        }
        father[s] = 0;
        
        // augment every possible blocking flow in the level graph
        for (bool existsBlckingFlow = dfs(s); existsBlckingFlow; existsBlckingFlow = dfs(s)) {
            int cfpath = c[father[t]][t] - f1[father[t]][t];
            for (int node = father[t]; node != s; node = father[node]) {
                if (cfpath > c[father[node]][node] - f1[father[node]][node]) {
                    cfpath = c[father[node]][node] - f1[father[node]][node];
                }
            }
            
            maxFlow += cfpath;
            
            for (int node = t; node != s; node = father[node]) {
                f1[father[node]][node] += cfpath;
                f1[node][father[node]] -= cfpath;
            }
            
            for (int i = 1; i <= V; ++ i) {
                father[i] = -1;
            }
            father[s] = 0;
        }
        
        for (int i = 1; i <= V; ++ i)
            levGf[i].clear();
    }
    
    return maxFlow;
}

int main() {
    readAndBuild();
    int F = maxFlowDinic();
    out << F << '\n';
    
    return 0;
}