#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define MAX_N 125
#define INF 0x3f3f3f3f

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

vector <int> G[MAX_N];
int In[MAX_N], Out[MAX_N];
int C[MAX_N][MAX_N], F[MAX_N][MAX_N], Cost[MAX_N][MAX_N];
int Dist[MAX_N], T[MAX_N];
int N, M, Sol;
int S, D;

void citire()
{
    scanf("%d %d",&N, &M);

    while(M--)
    {
        int a, b, c;
        scanf("%d %d %d",&a, &b, &c);

        Cost[a][b+N] = c;
        Cost[b+N][a] = -c;

        C[a][b+N] = INF;

        G[a].push_back(b+N);
        G[b+N].push_back(a);

        ++In[a];
        ++Out[b];

        Sol += c;
    }

    D = 2 * N + 1;
}

void pre()
{
    for(int i = 1; i <= N; ++i)
        if(In[i] < Out[i])
        {
            C[S][i] = Out[i] - In[i];
            G[S].push_back(i);
            G[i].push_back(S);
        }

        else if(Out[i] < In[i])
        {
            C[i+N][D] = In[i] - Out[i];
            G[D].push_back(i+N);
            G[i+N].push_back(D);
        }
}

int Bellman()
{
    for(int i = 1; i <= D; ++i)
        Dist[i] = INF;

    char viz[MAX_N];
    memset(viz, 0, sizeof viz);

    queue <int> Q;
    Q.push(S);
    Dist[S] = 0;
    viz[S] = 1;

    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        viz[nod] = 0;

        foreach(G[nod])
        {
            int act = *it;

            if(C[nod][act] > F[nod][act] && Dist[nod] + Cost[nod][act] < Dist[act])
            {
                Dist[act] = Dist[nod] + Cost[nod][act];

                T[act] = nod;

                if(viz[act] == 0)
                {
                    Q.push(act);
                    viz[act] = 1;
                }
            }
        }
    }

    return (Dist[D] != INF);
}

void flux()
{
    int fmin;
    while(Bellman())
    {
        fmin = INF;

        for(int i = D; i; i = T[i])
            fmin = min(fmin, C[T[i]][i] - F[T[i]][i]);

        for(int i = D; i; i = T[i])
            F[T[i]][i] += fmin,
            F[i][T[i]] -= fmin;

        Sol += fmin * Dist[D];
    }

    printf("%d\n",Sol);
}

int main()
{
    freopen("traseu.in","rt",stdin);
    freopen("traseu.out","wt",stdout);

    citire();
    pre();
    flux();
}