#include<bits/stdc++.h>
using namespace std;
ifstream fin("traseu.in");
ofstream fout("traseu.out");
const int INF = 1e5;
const int INF1 = 0x3f3f3f3f;
int N, M, Ans = 0;
int Cost[64][64], Grad[64], C[64][64], T[64], F[64][64];
vector<int> G[64];

int Dist[64], Viz[64];
queue<int> Q;

bool bf(){

    memset( Dist, INF1, sizeof(Dist) );
    Viz[0] = 1; Dist[0] = 0;
    Q.push( 0 );

    while( !Q.empty() ){

        int nod = Q.front();
        Q.pop();

        for( int i = 0; i < G[nod].size(); i++ ){

            int vecin = G[nod][i];

            if( Dist[vecin] > Dist[nod] + Cost[nod][vecin] && F[nod][vecin] < C[nod][vecin] ){

                Dist[vecin] = Dist[nod] + Cost[nod][vecin];
                T[vecin] = nod;

                if( Viz[vecin] == 0 )
                    Viz[vecin] = 1, Q.push( vecin );

            }

        }

        Viz[nod] = 0;

    }

    if( Dist[N + 1] != INF1 )
        return true;
    return false;

}

int main(){

    fin >> N >> M;

    memset( Cost, INF1, sizeof(Cost) );
    for( int i = 1; i <= N; i++ )
        Cost[i][i] = 0;

    for( int i = 1; i <= M; i++ ){
        int x, y, z; fin >> x >> y >> z;
        Ans += z;
        Cost[x][y] = z;
        Grad[x]--; Grad[y]++;
    }

    for( int k = 1; k <= N; k++ )
        for( int i = 1; i <= N; i++ )
            for( int j = 1; j <= N; j++ )
                if( i != j && Cost[i][j] > Cost[i][k] + Cost[k][j] )
                    Cost[i][j] = Cost[i][k] + Cost[k][j];

    for( int i = 1; i <= N; i++ ){

        if( Grad[i] > 0 ){
            G[0].push_back( i );
            C[0][i] = Grad[i];
            Cost[0][i] = 0;
        }

        if( Grad[i] < 0 ){
            G[i].push_back( N + 1 );
            C[i][N + 1] = -Grad[i];
            Cost[i][N + 1] = 0;
        }

    }

    for( int i = 1; i <= N; i++ ){

        if( Grad[i] <= 0 )
            continue;

        for( int j = 1; j <= N; j++ ){

            if( i == j || Grad[j] >= 0 )
                continue;

            G[i].push_back( j );
            G[j].push_back( i );
            C[i][j] = INF;
            Cost[j][i] = -Cost[i][j];

        }


    }

    while( bf() == true ){

        int minim = INF1;

        for( int i = N + 1; i != 0; i = T[i] )
            minim = min( minim, C[ T[i] ][i] - F[ T[i] ][i] );


        for( int i = N + 1; i != 0; i = T[i] ){
            F[ T[i] ][i] += minim;
            F[i][ T[i] ] -= minim;
            Ans += minim * Cost[ T[i] ][i];
        }

    }

    fout << Ans << "\n";

    return 0;
}