#include<bits/stdc++.h>

using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define inf 1000000000
int S,D,flux,N,M,nrE,rez,d[400],p[400];
int c[25202];
int v[25202];
int f[25202];
pair<int,int> mc[25202];
int q[160000],first,last;
vector<int> m[400];
bool viz[400],inq[400];

inline void add(int x) {
    if(inq[x]) return;
    inq[x] = viz[x] = 1;
    q[last++] = x;
}
inline int pop() {
    int x = q[first++];
    inq[x] = 0;
    return x;
}
inline void reset_stuff() {
    first = last = 0;
    for(int i = 1; i <= N; ++i) {
        viz[i] = inq[i] = 0;
        d[i] = 1000000000;
    }
    d[S] = 0;
}
inline void addEdge(int x,int y,int cap, int cost) {
    ++nrE;
    mc[nrE]=mp(x,y);
    c[nrE] = cap;
    v[nrE] = cost;
    m[x].pb(nrE);
    ++nrE;
    mc[nrE] = mp(y,x);
    c[nrE] = 0;
    v[nrE] = -cost;
    m[y].pb(nrE);
}
inline int getO(int x){
    if(x & 1) return x + 1;
    return x-1;
}
inline bool bfs() {
    reset_stuff();
    add(S);
    while(first < last) {
        int x = pop();
        if(x==D) continue;
        for(auto y : m[x]) {
            int ve = mc[y].sc;
            if(f[y] < c[y] && d[ve] > d[x] + v[y]) {
                add(ve); 
                p[ve] = y;
                d[ve] = d[x] + v[y];
            }
        }
    }
    return viz[D];
}
void update() {
    flux = inf;
    int curr = D;
    while(curr!=S) {
        int muc = p[curr];
        int par = mc[p[curr]].fs;
        if(c[muc] - f[muc] < flux) {
            flux = c[muc] - f[muc];
        }
        if(!flux) break;
        curr = par;
    }

    curr = D;
    while(curr!=S) {
        int muc = p[curr];
        int par = mc[p[curr]].fs;
        f[muc] += flux;
        f[getO(muc)] -= flux;
        curr = par;
    }
    rez += flux;
}
void flow() {
    while(true) {
        if(!bfs()) {
            break;
        }
        update();
    }
}

int main() {
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    scanf("%d%d",&N,&M);
    S=1;
    D=N;
    for(int i = 1; i <= M; ++i) {
        int x,y,z,t;
        scanf("%d%d%d",&x,&y,&z);
        addEdge(x,y,z,1);
    }
    flow();
 
    printf("%d",rez);
}