#include <bits/stdc++.h>

using namespace std;

const int VMAX = 62;
const int INF = 2e9;

vector <int> edges[VMAX];
int cost[VMAX][VMAX];
int flux[VMAX][VMAX];
int p[VMAX];

int in[VMAX];
int out[VMAX];

int dist[VMAX];
int realdist[VMAX];
int fakedist[VMAX];
bool inq[VMAX];
bool viz[VMAX];

int s, d;

bool bellman() {
    for ( int i = 0; i <= d; i ++ ) {
        dist[i] = INF;
    }
    queue <int> q;
    dist[s] = 0;
    q.push( s );
    while ( !q.empty() ) {
        int node = q.front();
        q.pop();
        for ( auto it : edges[node] ) {
            if ( flux[node][it] > 0 && dist[node] + cost[node][it] < dist[it] ) {
                dist[it] = dist[node] + cost[node][it];
                if ( !inq[it] ) {
                    q.push( it );
                    inq[it] = 1;
                }
            }
        }
    }
    return ( dist[d] != INF );
}
bool dijkstra() {
    for ( int i = 0; i <= d; i ++ ) {
        viz[i] = 0;
        realdist[i] = dist[i];
        fakedist[i] = INF;
        p[i] = -1;
    }
    priority_queue <pair<int, int>> pq;
    dist[s] = fakedist[s] = 0;
    p[s] = -2;
    pq.push( { 0, s } );
    while ( !pq.empty() ) {
        int node = pq.top().second;
        pq.pop();
        if ( viz[node] ) continue;
        viz[node] = 1;
        for ( auto it : edges[node] ) {
            if ( flux[node][it] > 0 && ( p[it] == -1 || fakedist[node] + realdist[node] + cost[node][it] - realdist[it] < fakedist[it] ) ) {
                p[it] = node;
                fakedist[it] = fakedist[node] + realdist[node] + cost[node][it] - realdist[it];
                dist[it] = dist[node] + cost[node][it];
                pq.push( { -fakedist[it], it } );
            }
        }
    }
    return ( fakedist[d] != INF );
}
int pump() {
    int c = 0, f = INF;
    for ( int i = d; i != s; i = p[i] ) {
        f = min( f, flux[p[i]][i] );
        c += cost[p[i]][i];
    }
    for ( int i = d; i != s; i = p[i] ) {
        flux[p[i]][i] -= f;
        flux[i][p[i]] += f;
    }
    return f * c;
}
int main() {
    ifstream fin( "traseu.in" );
    ofstream fout( "traseu.out" );
    int n, m, sum = 0;
    fin >> n >> m;
    s = 0, d = n + 1;
    for ( int i = 0; i < m; i ++ ) {
        int a, b, c;
        fin >> a >> b >> c;
        edges[a].push_back( b );
        edges[b].push_back( a );
        flux[a][b] = INF;
        cost[a][b] = c;
        cost[b][a] = -c;
        in[b] ++;
        out[a] ++;
        sum += c;
    }
    for ( int i = 1; i <= n; i ++ ) {
        if ( in[i] > out[i] ) {
            edges[s].push_back( i );
            edges[i].push_back( i );
            flux[s][i] = in[i] - out[i];
        } else if ( out[i] > in[i] ) {
            edges[i].push_back( d );
            edges[d].push_back( i );
            flux[i][d] = out[i] - in[i];
        }
    }
    bellman();
    int mincost = 0;
    while ( dijkstra() ) {
        mincost += pump();
    }
    fout << sum + mincost;
    return 0;
}