#include <fstream>
#include <bitset>
#include <queue>
#include <vector>

#define INF 0x3F3F3F3F

using namespace std;

bitset<64> inq;
vector<int> v[64];
int n, m, cost[64][64], cc[64][64], nodin[64], nodout[64], p[64], d[64], source, dest;


bool belmanFord()
{
    int nod;
    memset(d, INF, sizeof(d));
    
    queue<int> q;
    q.push(source);
    inq.set(source, 1);
    while (!q.empty()) {
        nod = q.front();
        q.pop();
        inq.set(nod, 0);
        
        for(vector<int>::iterator it = v[nod].begin(); it != v[nod].end(); ++it)
        {
            int val = d[nod] + cost[nod][*it];
            if (val < d[*it] && cc[nod][*it] > 0)
            {
                d[*it] = val;
                p[*it] = nod;
                if (inq.test(*it))
                    continue;
                q.push(*it);
                inq.set(*it, 1);
            }
        }
    }
    return d[dest] < INF;
}

int main()
{
    memset(cost, INF, sizeof(cost));
    memset(cc, INF, sizeof(cc));
    fstream fin("traseu.in", fstream::in);
    fin >> n >> m;
    int x, y, c, flow, nod;
    long result = 0;
    for (int i = 0; i<m;i++)
    {
        fin >> x >> y >> c;
        result += cost[x][y];
        v[x].push_back(y);
        v[y].push_back(x);
        cost[x][y] = c;
        cost[y][x] = -c;
        ++nodout[x];
        ++nodin[y];
    }
    fin.close();
    source = 0;
    dest = n+1;
    for(int i = 1;i<=n;i++)
        if (nodin[i] < nodout[i])
        {
            v[i].push_back(dest);
            v[dest].push_back(i);
            cc[i][dest] = nodout[i] - nodin[i];
        }
    else if (nodin[i] > nodout[i])
    {
        v[i].push_back(source);
        v[source].push_back(i);
        cc[source][i] = nodin[i] - nodout[i];
    }
    while (belmanFord())
    {
        flow = INF;
        for (nod = dest; nod != source; nod = p[nod])
            flow = min(flow, cc[p[nod]][nod]);
        for (nod = dest; nod != source; nod = p[nod])
        {
            cc[p[nod]][nod] -= flow;
            cc[nod][p[nod]] += flow;
        }
        result += flow * d[dest];
    }
    fstream fout("traseu.out", fstream::out);
    fout << result;
    fout.close();
    return 0;
}