#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
int s, t, n, m, grez[1001][1001], fp[1001], fm[1001], tata[1001], viz[1001], inf = 2e8, flux;
pair<int, int> g[1001][1001];
vector<int> adj[1001];
queue<int> q;
vector <pair <int, int> > taietura;


int main()
{
    ifstream fin("maxflow.in");
    ofstream fout("maxflow.out");
    int marginire = 1, conservare = 1;

    /*fin >> n >> s >> t >> m;
    int x, y, c, f;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c >> f;
        if (f > c || f < 0)
        {
            marginire = 0;
        }

        adj[x].push_back(y);
        adj[y].push_back(x);

        fp[x] = fp[x] + f;
        fm[y] = fm[y] + f;

        g[x][y] = {f, c};
        grez[x][y] = c - f;
        grez[y][x] = f;
    }


    for (int i = 1; i <= n; i++)
    {
        if (i != s && i != t && fm[i] != fp[i])
        {
            conservare = 0;
        }
    }

    if (conservare == 0 || marginire == 0)
    {
        cout << "NU";
        return 0;
    }

    cout << "DA" << endl;

    while(true)
    {
        int gasit = 0;
        for(int i = 1; i <= n; i++)
        {
            tata[i] = -1;
            viz[i] = 0;
        }
        q.push(s);
        viz[s] = 1;

        while(!q.empty())
        {
            int nod = q.front();
            q.pop();

            for (int i = 0; i < adj[nod].size(); i++)
            {
                if(grez[nod][adj[nod][i]] > 0 && viz[adj[nod][i]] == 0)
                {
                    tata[adj[nod][i]] = nod;
                    viz[adj[nod][i]] = 1;
                    q.push(adj[nod][i]);
                }
            }
        }

        if(tata[t] == -1)
        {
            break;
        }


        int minim = inf;

        int nod = t;
        while(tata[nod] != -1)
        {
            minim = min(minim, grez[tata[nod]][nod]);
            nod = tata[nod];
        }

        nod = t;
        while(tata[nod] != -1)
        {
            grez[tata[nod]][nod] -= minim;
            grez[nod][tata[nod]] += minim;
            nod = tata[nod];
        }


    }


    for(int i = 1; i <= n; i++)
    {
        if (i == s || tata[i] != -1)
        {
            for (int j = 0; j < adj[i].size(); j++)
            {
                if (g[i][adj[i][j]].second != 0 && tata[adj[i][j]] == -1)
                {
                    flux = flux + g[i][adj[i][j]].second;
                    taietura.push_back({i, adj[i][j]});
                }
            }
        }
    }

    cout << flux << endl;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < adj[i].size(); j++)
        {
            if (g[i][adj[i][j]].second != 0)
            {
                cout << i << " " << adj[i][j] << " " << grez[adj[i][j]][i] << endl;
            }
        }
    }

    cout << flux << endl;

    for (int i = 0; i < taietura.size(); i++)
    {
        cout << taietura[i].first << " " << taietura[i].second << endl;
    }*/

    fin >> n >> m;
    int x, y, c, f;

    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;

        adj[x].push_back(y);
        adj[y].push_back(x);

        g[x][y] = {0, c};
        grez[x][y] = c;
    }

    while(true)
    {
        int gasit = 0;
        for(int i = 1; i <= n; i++)
        {
            tata[i] = -1;
            viz[i] = 0;
        }
        q.push(1);
        viz[1] = 1;

        while(!q.empty())
        {
            int nod = q.front();
            q.pop();

            for (int i = 0; i < adj[nod].size(); i++)
            {
                if(grez[nod][adj[nod][i]] > 0 && viz[adj[nod][i]] == 0)
                {
                    tata[adj[nod][i]] = nod;
                    viz[adj[nod][i]] = 1;
                    q.push(adj[nod][i]);
                }
            }
        }

        if(tata[n] == -1)
        {
            break;
        }


        int minim = inf;

        int nod = n;
        while(tata[nod] != -1)
        {
            minim = min(minim, grez[tata[nod]][nod]);
            nod = tata[nod];
        }

        nod = n;
        while(tata[nod] != -1)
        {
            grez[tata[nod]][nod] -= minim;
            grez[nod][tata[nod]] += minim;
            nod = tata[nod];
        }

    }


    for(int i = 1; i <= n; i++)
    {
        if (i == 1 || tata[i] != -1)
        {
            for (int j = 0; j < adj[i].size(); j++)
            {
                if (g[i][adj[i][j]].second != 0 && tata[adj[i][j]] == -1)
                {
                    flux = flux + g[i][adj[i][j]].second;
                }
            }
        }
    }

    fout << flux;


    fin.close();

    return 0;
}