#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int Nmax = 62;
const int inf = 1e9;

struct NODE
{
    int nod;
    int dist;

    NODE( const int a = 0, const int b = 0 ) : nod( a ), dist( b ) {}

    bool operator < ( const NODE X ) const
    {
        return dist > X.dist;
    }
};

vector <int> G[Nmax];
priority_queue <NODE> MinHeap;
int grad_in[Nmax], grad_out[Nmax];
int D[Nmax][Nmax];
int C[Nmax][Nmax];
int F[Nmax][Nmax];
int Cost[Nmax][Nmax];
int tata[Nmax], dist[Nmax], in_q[Nmax], coada[Nmax];

int N, M, source, sink;

void RoyFloyd()
{
    for ( int k = 1; k <= N; ++k )
            for ( int i = 1; i <= N; ++i )
                    for ( int j = 1; j <= N; ++j )
                            D[i][j] = min( D[i][j], D[i][k] + D[k][j] );
}

void add_edge( int x, int y, int cap, int cost )
{
    G[x].push_back( y );
    G[y].push_back( x );

    C[x][y] = cap;

    Cost[x][y] = +cost;
    Cost[y][x] = -cost;
}

void build_network()
{
    for ( int i = 1; i <= N; ++i )
    {
        if ( grad_in[i] > grad_out[i] )
        {
            add_edge( source, i, grad_in[i] - grad_out[i], 0 );
        }

        if ( grad_out[i] > grad_in[i] )
        {
            add_edge( i, sink, grad_out[i] - grad_in[i], 0 );
        }
    }

    for ( int i = 1; i <= N; ++i )
    {
        for ( int j = 1; j <= N; ++j )
        {
            if ( grad_out[i] < grad_in[i] && grad_out[j] > grad_in[j] )
                    add_edge( i, j, inf, D[i][j] );
        }
    }
}

void BellmanFord()
{
    for ( int i = 0; i <= N + 1; ++i )
    {
        dist[i] = inf;
        in_q[i] = 0;
    }

    int st, dr;
    dist[source] = 0;
    in_q[source] = 1;
    coada[st = dr = 1] = source;

    while ( st <= dr )
    {
        int nod = coada[ st++ ];
        in_q[nod] = 0;

        for ( auto x: G[nod] )
        {
            if ( dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] > F[nod][x] )
            {
                if ( C[nod][x] <= F[nod][x] ) cout<<"ERROR";

                dist[x] = dist[nod] + Cost[nod][x];

                if ( !in_q[x] )
                {
                    in_q[x] = 1;
                    coada[ ++dr ] = x;
                }
            }
        }
    }
}

void init()
{
    for ( int i = 0; i <= N + 1; ++i )
    {
        for ( auto x: G[i] )
        {
            if ( dist[x] != inf && dist[i] != inf )
            {
                Cost[i][x] += dist[i] - dist[x];
            }
        }
    }

    for ( int i = 0; i <= N + 1; ++i )
    {
        dist[i] = inf;
        tata[i] = 0;
    }

    dist[source] = 0;
}

int Dijkstra()
{
    init();

    MinHeap.push( NODE( source, 0 ) );

    while ( MinHeap.size() )
    {
        int nod = MinHeap.top().nod;
        int ddd = MinHeap.top().dist;

        MinHeap.pop();

        if ( dist[nod] != ddd) continue;

        for ( auto x: G[nod] )
        {
            if ( dist[x] > dist[nod] + Cost[nod][x] && C[nod][x] > F[nod][x] )
            {
                dist[x] = dist[nod] + Cost[nod][x];
                tata[x] = nod;
                MinHeap.push( NODE( x, dist[x] ) );
            }
        }
    }

    return ( dist[sink] < inf );
}

int Edmonds_Karp()
{
    int flow = 0;
    int costFlow = 0;
    int destD = dist[sink];
    int fmin;

    while ( Dijkstra() )
    {
        fmin = inf;

        for ( int nod = sink; nod != source; nod = tata[nod] )
                fmin = min( fmin, C[ tata[nod] ][nod] - F[ tata[nod] ][nod] );

        for ( int nod = sink; nod != source; nod = tata[nod] )
        {
            F[ tata[nod] ][nod] += fmin;
            F[nod][ tata[nod] ] -= fmin;
        }

        destD += dist[sink];
        costFlow += fmin * destD;
        flow += fmin;
    }

    return costFlow;
}

int main()
{
    ifstream f("traseu.in");
    ofstream g("traseu.out");

    f >> N >> M;

    source = 0;
    sink = N + 1;

    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    D[i][j] = inf;

    int sum = 0;

    for ( int i = 1, a, b, c; i <= M; ++i )
    {
        f >> a >> b >> c;

        D[a][b] = c;
        grad_in[b]++;
        grad_out[a]++;
        sum += c;
    }

    RoyFloyd();
    build_network();
    BellmanFord();
    g << Edmonds_Karp() + sum << "\n";

    return 0;
}