#include <bits/stdc++.h>
#define N 65

using namespace std;

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

vector<pair<int,int> > graf[N] ;
int c[N][N] , grad[N] , dist[N] , parinte[N] , flux[N][N] ;
int sol , n , m ;

void citire()
{
    int i , x , y , z ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> z ;
        graf[x].push_back(make_pair(y,z)) ;
        graf[y].push_back(make_pair(x,-z)) ;
        c[x][y] = N ;
        grad[y]++ ;
        grad[x]-- ;
        sol = sol+z;
    }
    for ( i = 1 ; i <= n ; i++ )
    {
        if ( grad[i] > 0 )
        {
            graf[0].push_back(make_pair(i,0)) ;
            c[0][i] = grad[i] ;
        }
        else
        {
            graf[i].push_back(make_pair(n+1,0)) ;
            c[i][n+1] = -grad[i] ;
        }
    }
}

int dij()
{
    int nod ;
    queue<int> Q ;
    memset(dist,0x3f3f3f3f,sizeof(dist)) ;
    memset(parinte,0,sizeof(parinte)) ;
    Q.push(0) ;
    dist[0] = 0 ;
    while ( !Q.empty())
    {
        nod = Q.front() ;
        Q.pop() ;
        for ( auto vec : graf[nod] )
        {
            if ( c[nod][vec.first] > flux[nod][vec.first] && dist[vec.first] > dist[nod]+vec.second)
            {
                dist[vec.first] = dist[nod] + vec.second ;
                Q.push(vec.first) ;
                parinte[vec.first] = nod ;
            }
        }
    }
    if ( dist[n+1] == 0x3f3f3f3f )
        return 0 ;
    for ( nod = n+1 ; nod != 0 ; nod = parinte[nod] )
    {
        flux[parinte[nod]][nod]++ ;
        flux[nod][parinte[nod]]-- ;
    }
    return dist[n+1] ;
}

int main()
{
    citire() ;
    int ok = 1 ;
    while ( ok )
    {
        ok = dij() ;
        sol = sol+ok ;
    }
    fout << sol ;
}