#include<fstream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std ;

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

#define maxn 61
#define inf 100000

int N, M ;

int dist[maxn][maxn], val[maxn];
int cap[maxn][maxn], ocupat[maxn][maxn], tata[maxn];

int dmin[maxn], rez ;

bool sel[maxn] ;
queue<int> coada ;

bool flux()
{
    for(int i = 0; i <= N + 1; ++i )
        dmin[i] = inf ;

    memset( sel, false, sizeof(sel) ) ;
    memset( tata, 0, sizeof(tata) ) ;

    dmin[0] = 0 ;
    coada.push( 0 ) ;
    sel[0] = true ;

    while( coada.empty() == false )
    {
        int nod = coada.front() ;
        sel[nod] = false ;
        coada.pop() ;

        for(int i = 0; i <= N + 1; ++i )
        {
            if( ocupat[nod][i] < cap[nod][i] && dmin[nod] + dist[nod][i] < dmin[i] )
            {
                dmin[i] = dmin[nod] + dist[nod][i] ;
                tata[i] = nod ;

                if( sel[i] == false )
                {
                    coada.push(i) ;
                    sel[i] = true ;
                }
            }
        }
    }

    if( dmin[ N + 1 ] == inf )
        return false ;

    rez += dmin[ N + 1 ] ;

    int nod = N + 1 ;
    while( nod != 0 )
    {
        ++ocupat[ tata[nod] ][nod] ;
        --ocupat[nod][ tata[nod] ] ;
        nod = tata[nod] ;
    }

    return true ;
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= N; ++i )
        for(int j = 1; j <= N; ++j )
            dist[i][j] = inf ;

    for(int i = 1; i <= N; ++i )
        dist[i][i] = 0 ;

    for(int i = 1; i <= M; ++i )
    {
        int nod1, nod2, cost ;
        fin >> nod1 >> nod2 >> cost;

        dist[nod1][nod2] = cost ;
        dist[nod2][nod1] = -cost ;

        ++val[nod1] ;
        --val[nod2] ;

        rez += cost ;
    }

    for(int i = 1; i <= N; ++i )
    {
        if( val[i] < 0 )
            cap[0][i] = -val[i] ;

        if( val[i] > 0 )
            cap[i][ N + 1 ] = val[i] ;
    }

    for(int i = 1; i <= N; ++i )
        for(int j = 1; j <= N; ++j )
            if( dist[i][j] > 0 )
                cap[i][j] = inf ;

    while( flux() ) ;

    fout << rez ;

    return 0 ;
}