/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "traseu.in" ;
const char OUT [ ] = "traseu.out" ;
const int MAX = 80 ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

using namespace std ;

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

int I [ MAX ] ;
int E [ MAX ] ;
int IQ [ MAX ] ;
int dist [ MAX ] ;
int tata [ MAX ] ;
int flux [ MAX ] [ MAX ] ;
int cap [ MAX ] [ MAX ] ;
int cost [ MAX ] [ MAX ] ;
int CET ;
int S ;
int D ;
int local_flox ;

vector < int > gr [ MAX ] ;
queue < int > Q ;

inline void baga ( int Source , int Dest , int Cst , int Capacitate )
{
    gr [ Source ].pb ( Dest ) ;
    gr [ Dest ].pb ( Source ) ;
    cost [ Source ] [ Dest ] = Cst ;
    cost [ Dest ] [ Source ] = -Cst ;
    cap [ Source ] [ Dest ] = Capacitate ;
}

inline int BF ( )
{
    FORN ( i , 1 , 62 ) dist [ i ] = 1 << 30 ;
    memset ( IQ , 0 , sizeof ( IQ ) ) ;

    Q.push ( S ) ;
    IQ [ S ] = 1 ;
    dist [ S ] = 0 ;

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

        for ( auto x : gr [ nod ] )
            if ( cap [ nod ] [ x ] > flux [ nod ] [ x ] ){
                if ( dist [ x ] > dist [ nod ] + cost [ nod ] [ x ] ) {
                    dist [ x ] = dist [ nod ] + cost [ nod ] [ x ] ;
                    tata [ x ] = nod ;
                    if ( ! IQ [ x ] ) {
                        IQ [ x ] = 1 ;
                        Q.push ( x ) ;
                    }
                }
            }
    }

    local_flox = 0 ;

    if ( dist [ D ] != 1 << 30 )
    {
         local_flox = 1 << 30 ;

        for ( int i = D ; tata [ i ] ; i = tata [ i ] )
        {
             local_flox = min (  local_flox , cap [ tata [ i ] ] [ i ] - flux [ tata [ i ] ] [ i ] ) ;
        }

        for ( int i = D ; tata [ i ] ; i = tata [ i ] )
        {
            flux [ tata [ i ] ] [ i ] +=  local_flox ;
            flux [ i ] [ tata [ i ] ] -=  local_flox ;
        }
    }

    return local_flox != 0 ;
}

int main ( void )
{
    int n , m ;
    cin >> n >> m ;

    S = 0 ;
    D = n + 1 ;

    while ( m -- )
    {
        int x , y , cost ;
        cin >> x >> y >> cost ;
        CET += cost ;
        I [ y ] ++ ;
        E [ x ] ++ ;

        baga ( x , y , cost , 1 << 30 ) ;
    }

    FORN ( i , 1 , n )
    {
        if ( I [ i ] - E [ i ] > 0 ) baga ( S , i , 0 , abs ( I [ i ] - E [ i ] ) ) ;
        if ( I [ i ] - E [ i ] < 0 ) baga ( i , D , 0 , abs ( I [ i ] - E [ i ] ) ) ;
    }

    while ( BF ( ) )
        CET += dist [ D ] * local_flox ;

    cout << CET << '\n' ;

    return 0;
}