#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
#define NMAX 64
#define INF 0x3f3f3f3f
#define pb push_back
 
int Cost[NMAX][NMAX], C[NMAX][NMAX], F[NMAX][NMAX], Int[NMAX], Ext[NMAX], T[NMAX], Dist[NMAX];
int N, M, i, x, y, cost, S, D, CostMin, Nod, FluxCt;
vector< int > G[NMAX];
bool Used[NMAX];
 
inline bool BF()
{
    memset( T, 0, sizeof(T) );
    memset( Dist, INF, sizeof(Dist) );
    Dist[S] = 0;
    memset( Used, false, sizeof(Used) );
    queue< int > Q;
    Q.push( S );
    Used[S] = true;
     
    while( !Q.empty() )
    {
        Nod = Q.front();
        Q.pop();
        Used[Nod] = false;
         
        for( vector< int >::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
            if( F[Nod][*it] < C[Nod][*it] && Dist[*it] > Dist[Nod] + Cost[Nod][*it] )
            {
                Dist[*it] = Dist[Nod] + Cost[Nod][*it];
                T[*it] = Nod;
                if( !Used[*it] )
                {
                    Used[*it] = true;
                    Q.push( *it );
                }
            }
    }
     
    return ( T[D] != 0 );
}
 
int main()
{
    freopen("traseu.in", "r", stdin);
    freopen("traseu.out", "w", stdout);
     
    scanf("%d%d", &N, &M );
    memset( C, 0, sizeof(C) );
    memset( F, 0, sizeof(F) );
    for( ; M--; )
    {
        scanf("%d%d%d", &x, &y, &cost );
        ++Int[y], ++Ext[x];
        C[x][y] = INF;
        Cost[x][y] = cost;
        Cost[y][x] = -cost;
        G[x].pb( y );
        G[y].pb( x );
         
        CostMin += cost;
    }
     
    S = 0, D = N + 1;
    for( i = 1; i <= N; ++i )
        if( Int[i] > Ext[i] )
        {
            G[S].pb( i );
            G[i].pb( S );
            C[S][i] = Int[i] - Ext[i];
        }
        else if( Ext[i] > Int[i] )
        {
            G[D].pb( i );
            G[i].pb( D );
            C[i][D] = Ext[i] - Int[i];
        }
     
    while( BF() )
    {
        FluxCt = INF;
        for( Nod = D; Nod != S; Nod = T[Nod] )
            FluxCt = min( FluxCt, C[ T[Nod] ][Nod] - F[ T[Nod] ][Nod] );
        if( !FluxCt ) continue;
        for( Nod = D; Nod != S; Nod = T[Nod] )
            F[ T[Nod] ][Nod] += FluxCt, F[Nod][ T[Nod] ] -= FluxCt;
        CostMin += FluxCt * Dist[D];
    }
     
    printf("%d\n", CostMin );
     
    return 0;
}