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

typedef struct { int x,c; } node;

struct cmp_node
{
    bool operator () (const node x,const node y)
    {
        return x.c >= y.c;
    }
};

node make_node(int x,int c)
{
    node now;
    now.x = x;
    now.c = c;
    return now;
}

priority_queue<node,vector<node>,cmp_node> Q;

ifstream F("traseu.in");
ofstream G("traseu.out");

const int Nmax = 70;
const int value = 1010;

int N,M,dist_now[Nmax],dist_last[Nmax];
int capacity[Nmax][Nmax],cost[Nmax][Nmax];
vector<int> V[Nmax];
int last[Nmax],dist_real[Nmax];
int total_flow,total_cost;

#define IT(type) vector<type>::iterator

void Bellman_pq(int start,int target)
{
    memset(last,0,sizeof(last));
    memset(dist_now,0x3f,sizeof(dist_now));

    dist_now[start] = 0;
    last[start] = -1;
    Q.push( make_node(start,dist_now[start]) );

    while ( Q.size() )
    {
        node now = Q.top();
        Q.pop();

        if ( dist_now[now.x] != now.c )
            continue;

        for (IT(int) it=V[now.x].begin();it!=V[now.x].end();++it)
            if ( capacity[now.x][*it] != 0 )
                if ( dist_now[*it] > dist_now[now.x] + cost[now.x][*it] )
                {
                    dist_now[*it] = dist_now[now.x] + cost[now.x][*it];
                    last[*it] = now.x;
                    Q.push( make_node( *it , dist_now[now.x] + cost[now.x][*it] ) );
                }
    }
    memcpy(dist_real,dist_now,sizeof(dist_now));
}

int Dijkstra_pq(int start,int target)
{
    memset(last,0,sizeof(last));
    memcpy(dist_last,dist_real,sizeof(dist_real));
    memset(dist_now,0x3f,sizeof(dist_now));
    memset(dist_real,0x3f,sizeof(dist_real));

    dist_now[start] = 0;
    dist_real[start] = 0;
    last[start] = -1;
    Q.push( make_node(start,dist_now[start]) );

    while ( Q.size() )
    {
        node now = Q.top();
        Q.pop();

        if ( dist_now[now.x] != now.c )
            continue;

        for (IT(int) it=V[now.x].begin();it!=V[now.x].end();++it)
            if ( capacity[now.x][*it] != 0 )
            {
                int distance = dist_now[now.x] + cost[now.x][*it];
                distance += dist_last[now.x] - dist_last[*it];
                if ( dist_now[*it] > distance )
                {
                    dist_real[*it] = dist_real[now.x] + cost[now.x][*it];
                    last[*it] = now.x;
                    dist_now[*it] = distance;
                    Q.push( make_node( *it , distance ) );
                }
            }
    }
    return last[target] != 0;
}

int g1[Nmax],g2[Nmax],ans;

int main()
{
    F>>N>>M;
    int source = 1;
    int target = N+2;
    for (int i=1,x,y,cc;i<=M;++i)
    {
        F>>x>>y>>cc;
        x++, y++;
        if ( capacity[x][y] == 0 && capacity[y][x] == 0 )
        {
            V[ x ].push_back( y );
            V[ y ].push_back( x );
        }
        capacity[x][y] = 1<<30;
        cost[x][y] = cc;
        cost[y][x] = -cc;
        g1[y]++;
        g2[x]++;
        ans += cc;
    }
    for (int i=2;i<=N+1;++i)
        if ( g1[i] > g2[i] )
        {
            capacity[source][i] = g1[i] - g2[i];
            cost[source][i] = cost[i][source] = 0;
            V[ source ].push_back( i );
            V[ i ].push_back( source );
        }
        else if ( g1[i] < g2[i] )
        {
            capacity[i][target] = g2[i] - g1[i];
            cost[target][i] = cost[i][target] = 0;
            V[ target ].push_back( i );
            V[ i ].push_back( target );
        }
    N += 2;

    Bellman_pq(source,target);
    while ( Dijkstra_pq(source,target) != 0 )
    {
        int Cmin = capacity[last[target]][target];
        for (int now=last[target];now!=source;now=last[now])
            Cmin = min( Cmin , capacity[last[now]][now] );

        total_flow += Cmin;

        for (int now=last[target];now!=source;now=last[now])
        {
            capacity[last[now]][now] -= Cmin;
            capacity[now][last[now]] += Cmin;
        }
        capacity[last[target]][target] -= Cmin;
        total_cost += dist_real[target] * Cmin;
    }

    ans += total_cost;
    G<<ans<<'\n';
}