#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];

bool 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();
            
    while(search(n,v,p)){
                   int min; min=INF;
                   int i; i=n;
                   while(i!=1){
                               int r; r=p[i];
                               if(min>C[r][i]) min=C[r][i];
                               i=r;
                               }
                          
                   i=n;
                   while(i!=1){
                                  int r; r=p[i];
                                  C[r][i]-=min;
                                  C[i][r]+=min;
                                  i=r;
                                  }              
                   }
    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();
    }
    
bool search(int n, vector<int> v[], int p[]){
    bool vis[n+1];
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(1);
    while(!q.empty()){
                    int r;
                    r=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(to==n) return true;
                                              q.push(to);
                                              }
                            }
                    }
    return false;
    }