//Roy-Dloyd 589
/*#include <iostream>
#include <fstream>
#define oo 10000
using namespace std;
ifstream fin("roy-floyd.in");
ofstream fout("roy-floyd.out");
int n, m, D[101][101], T[101][101], h[101][101];
int x, y, c;
void afisare(int mat[101][101], int n) {
    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++)
            if (mat[i][j] != oo)
            {

                fout << mat[i][j] << " ";
            }
            else
            {

                fout << -1 << ' ';
            }
        fout << endl;
    }
}
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++) {
            if (i != j)
                h[i][j] = oo;
        }
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        h[x][y] = c;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (h[i][j] != oo && i != j)
                T[i][j] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            D[i][j] = h[i][j];
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    T[i][j] = T[k][j];
                }
    //afisare(T, n);
    //cout << endl;
    afisare(D, n);
    return 0;
}*/


//RF 1652
/*#include <iostream>
#define oo 1000000
using namespace std;
int n, m, D[101][101], T[101][101], h[101][101];
int main()
{
    cin >> n >> m;
    int x, y, c;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++) {
            if (i != j)
                h[i][j] = oo;
        }
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> c;
        h[x][y] = c;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (h[i][j] != oo && i != j)
                T[i][j] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            D[i][j] = h[i][j];
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    T[i][j] = T[k][j];
                }
    int ct = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (h[i][j] == D[i][j] && h[i][j] != 0 && D[i][j] != 0 && h[i][j] != oo && D[i][j] != oo)
                ct++;
        }
    cout << ct;
    return 0;
}*/

//Firma 591
/*#include <iostream>
#include <fstream>
#include <climits>
#define oo 100000
using namespace std;
ifstream in("firma.in");
ofstream out("firma.out");
int n, m, D[101][101], T[101][101], h[101][101];
int main()
{
    in >> n >> m;
    int x, y, c;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= 100; j++) {
            if (i != j)
                h[i][j] = oo;
        }
    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        h[x][y] = c;
        h[y][x] = c;
    }
    for(int i=1;i<=n;++i)
        for (int j = 1; j <= n; ++j)
        {
            D[i][j] = h[i][j];
            if (D[i][j] != oo && i != j)
                T[i][j] = i;
        }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    T[i][j] = T[k][j];
                }
    int suma = 0, minim = oo, a;
    for (int s = 1; s <= n; ++s)
    {
        //cout << s << ": ";
        for (int j = 1; j <= n; j++)
        {
            //cout << D[s][j] << ' ';
            suma += D[s][j];
        }
        cout << endl << suma << endl;
        if (minim > suma)
        {
            minim = suma;
            a = s;
        }
        suma = 0;
    }
    out << a;
    return 0;
}*/


//Flux maxim infoarena
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
int a[101][101], c[101][101], f[101][101];
int viz[101], T[101];
int n, m, lung, minim;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
struct arc { int n1, n2; };
arc drum[101];
int bf()
{
    int i, j;
    queue <int> q;
    fill(viz, viz + 101, 0); fill(T, T + 101, 0);
    q.push(1);
        viz[1] = 1;
    while (q.empty() != 1)
    {
        i = q.front();
        if (i == n)
            return 1;
        q.pop();
        for (j = 1; j <= n; j++)
        {
            if (viz[j] == 0 && c[i][j] - f[i][j] > 0)
            {//arc parcurs in sens direct
                viz[j] = 1;
                T[j] = i;
                q.push(j);
            }
            if (viz[j] == 0 && f[j][i] > 0)
            {//arc parcurs in sens invers
                viz[j] = 1;
                T[j] = i;
                q.push(j);
            }
        }
    }
    return 0;
}
void calcdrum()
{
    int i = 0, b = n, a;
    minim = 10000000;
    a = T[b];
    while (a != 0)
    {
        drum[i].n1 = a;
        drum[i].n2 = b;
        if (c[a][b] > f[a][b])
        {
            if (minim > c[a][b] - f[a][b])
                minim = c[a][b] - f[a][b];
        }
        else
            if (minim > f[b][a])
                minim = f[b][a];
        i++;
        b = a;
        a = T[b];
    }
    lung = i;
}


int main()
{
    int i, j, k, ok = 1;
    fin >> n >> m;
    for (i = 0; i < m; i++)
    {
        fin >> i >> j;
        fin >> c[i][j];
    }
    while (ok == 1)
    {
        ok = bf(); //returneaza 1 daca gaseste un drum
        if (ok == 1)
        {
            calcdrum(); //calculeaza si minimul
            //cout << "\n\ngasit un drum de lungime " << lung;
            //cout << " capacitate reziduala " << minim << endl;
            //cout << "format din arcele: ";
            for (k = 0; k < lung; k++)
            {
                i = drum[k].n1;
                j = drum[k].n2;
                //cout << i << '-' << j << " , ";
                if (c[i][j] - f[i][j] > 0)
                    f[i][j] += minim;
                else
                    f[j][i] -= minim;
            }
        }
    }
    int fluxmax = 0;
    for (i = 1; i <= n; i++)
        fluxmax += f[1][i];
    //cout << "\n\nflux maxim= " << fluxmax << endl;
    //cout << "starea fiecarui arc:capacitate/flux\n";
    int suma = 0;
    int maxflow = 0;
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            if (c[i][j] > 0)
            {
                suma += f[i][j];
                cout << '(' << i << '-' << j << "):";
                cout << c[i][j] << '/' << f[i][j] << endl;
            }
        if (maxflow < suma)
            maxflow = suma;
        suma = 0;
    }
    fout << maxflow;
    return 0;
}