#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<cstring>
using namespace std;
#define INF 100000000
#define MAX 1024

int F[MAX][MAX], C[MAX][MAX];

int search(int n, vector<int> v[], int p[]); 

int main(){
    int n,m;
    ifstream cinr("maxflow.in");
    cinr >> n >> m;
    vector<int> v[n+1];
    int p[n+1];
    for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                    F[i][j]=C[i][j]=0;
    
    for(int i=0; i<m; i++){
            int a,b,c;
            cinr >> a >> b >> c;
            v[a].push_back(b);
            F[a][b]+=c; C[a][b]+=c;
            v[b].push_back(a);
            } cinr.close();
            
    int min=search(n,v,p);
    while(p[n]!=0){
                   int i=n;
                   while(i!=1){
                                  int r; r=p[i];
                                  C[r][i]-=min;
                                  C[i][r]+=min;
                                  i=r;
                                  }              
                   min=search(n,v,p);
                   }
    int sum=0;
    for(int i=1; i<=n; i++){
            sum+=F[1][i]-C[1][i];
            }
    ofstream cour("maxflow.out");
    cour << sum;
    cour.close();
    }
    
int search(int n, vector<int> v[], int p[]){
    bool vis[n+1];
    memset(vis,0,sizeof(vis));
     for(int i=1; i<=n; i++) p[i]=0;
    queue<int> q;
    q.push(1); q.push(INF);
    int min;
    while(!q.empty()){
                    int r;
                    r=q.front(); q.pop();
                    min=q.front(); q.pop();
                    vis[r]=true;
                    for(int i=0; i<v[r].size(); i++){
                            int to;
                            to=v[r][i];
                            if(!vis[to] && C[r][to]!=0){
                                              p[to]=r;
                                              if(C[r][to]<min) min=C[r][to];
                                              if(to==n) return min;
                                              q.push(to); q.push(min);
                                              }
                            }
                    }
    return min;
    }