#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define fr first
#define sc second
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int nmax = 1005;

int n, m, capacity[nmax][nmax], maxi;

vector<int>nod[nmax];
vector<pair<int,int>>parent(nmax);

void dfs(int s, int par){
    parent[s].fr = par;
    if(s != 1) parent[s].sc = min(parent[par].sc, capacity[par][s]);
    else parent[1].sc = 1e6;
    for(auto it : nod[s]){
        if(parent[it].fr == -1 && capacity[s][it] >= maxi){
            dfs(it, s);
        }
    }
}

int maxflow(int s, int t){
    int flow = 0;
    while(maxi >= 2){
        maxi = maxi / 2;
        while(true){
            for(int i=1;i<=n;i++) parent[i].fr = -1;
            dfs(s, 0);
            if(parent[t].fr == -1) break;
            else{
                flow += parent[t].sc;
                int curr = t;
                while(parent[curr].fr != 0){
                    capacity[parent[curr].fr][curr] -= parent[t].sc;
                    capacity[curr][parent[curr].fr] += parent[t].sc;
                    curr = parent[curr].fr;
                }
            }
        }
    }
    return flow;
}

int32_t main(){
    //ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        nod[x].push_back(y);
        nod[y].push_back(x);
        capacity[x][y] = z;
        maxi = max(maxi, z);
    }
    maxi = 2 * maxi;
    cout << maxflow(1, n) << '\n';
}