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

using namespace std;

const int NSIZE = 60 + 10;
const int inf = 1 << 30;

int N , M , x , y , z , i , ci , fmin , flow , S , D;
int d[NSIZE] , flag[NSIZE] , nxt[NSIZE] , in[NSIZE] , out[NSIZE];
int p[NSIZE][NSIZE] , c[NSIZE][NSIZE] , f[NSIZE][NSIZE];
vector < int > g[NSIZE];
queue < int > inQ;

void add(int x,int y,int z,int cap)
{
    g[x].push_back(y);
    g[y].push_back(x);

    c[x][y] += cap;
    p[x][y] = z;
    p[y][x] = -z;
}

bool bellman()
{
    for (int i=1;i<=N;++i)
    d[i] = inf;

    d[S] = 0;
    inQ.push(S);
    flag[S] = 1;

    while (!inQ.empty())
    {
        int crt = inQ.front();
        inQ.pop() , flag[crt] = 0;

        for (int i = 0;i < g[crt].size();++i)
        {
            int to = g[crt][i];

            if (f[crt][to] < c[crt][to] && d[to] > d[crt] + p[crt][to])
            {
                d[to] = d[crt] + p[crt][to];
                nxt[to] = crt;

                if (flag[to] == 0)
                {
                    inQ.push(to);
                    flag[to] = 1;
                }
            }
        }
    }

    if (d[D] == inf) return false;
    return true;
}

int main()
{

ifstream fin("traseu.in");
ofstream fout("traseu.out");

fin >> N >> M;
S = 0 , D = N + 1;

for (i=1;i<=M;++i)
{
    fin >> x >> y >> z;
    flow += z;

    in[y] += 1 , out[x] += 1;
    add(x , y , z , inf);
}

for (i=1;i<=N;++i)
(in[i] > out[i]) ? add(S , i , 0 , in[i] - out[i]) : add(i , D , 0 , out[i] - in[i]);

N += 1;

while (bellman())
{
    fmin = inf;

    for (i = D ; i != S ; i = nxt[i])
    {
        int to = nxt[i];
        fmin = min(fmin , c[to][i] - f[to][i]);
    }

    flow += fmin * d[D];

    for (i = D ; i != S ; i = nxt[i])
    {
        int to = nxt[i];
        f[to][i] += fmin;
        f[i][to] -= fmin;
    }
}

fout << flow << '\n';

return 0;
}