#include <bits/stdc++.h>

#define INF 100000000
#define source 0

using namespace std;

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

int N, M, D[64], A[64][64], intrare[64], iesire[64];
int capacity[64][64], flow[64][64], cost[64][64], T[64], H[64];
int solution;
int destination;
bitset<64> v;
vector<int>L[64];
queue <int>Q;

inline void royFloyd()
{
    for(int i = 1; i <= N; i ++)
    {
        for(int j = 1; j <= M; j ++)
        {
            if(A[i][j] == 0 && i != j)
            {
                A[i][j] = INF;
            }
        }
    }

    for(int k = 1; k <= N; k ++)
    {
        for(int i = 1; i <= N; i ++)
        {
            for(int j = 1; j <= N; j ++)
            {
                if(A[i][j] > A[i][k] + A[k][j])
                {
                    A[i][j] = A[i][k] + A[k][j];
                }
            }
        }
    }
}

inline bool bellmanFord()
{
    for(int i = 1; i <= N + 1; i ++)
    {
        D[i] = INF;
        v[i] = 0;
    }

    Q.push(source);
    D[source] = 0;

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        v[node] = 0;

        for(int i = 0; i < L[node].size(); i ++)
        {
            int neighbour = L[node][i];

            if(D[neighbour] > D[node] + cost[node][neighbour] && capacity[node][neighbour] > flow[node][neighbour])
            {
                D[neighbour] = D[node] + cost[node][neighbour];
                T[neighbour] = node;

                if(v[neighbour] == 0)
                {
                    Q.push(neighbour);
                    v[neighbour] = 1;
                }
            }
        }
    }

    return D[destination] != INF;
}

int main()
{
    fin >> N >> M;
    destination = N + 1;

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

        A[a][b] = c;

        iesire[a] ++;
        intrare[b] ++;

        solution += c;
    }

    royFloyd();

    for(int i = 1; i <= N; i ++)
    {
        if(iesire[i] < intrare[i])
        {
            L[source].push_back(i);
            L[i].push_back(source);
            capacity[source][i] = intrare[i] - iesire[i];
            H[i] = 1;
        }
        else
        {
            if(iesire[i] >= intrare[i])
            {
                L[destination].push_back(i);
                L[i].push_back(destination);
                capacity[i][destination] = iesire[i] - intrare[i];
                H[i] = 2;
            }
        }
    }
    for(int i = 1; i <= N ; i ++)
    {
        for(int j = 1; j <= N; j ++)
        {
            if(i == j)
            {
                continue;
            }
            if(H[i] != H[j])
            {
                L[i].push_back(j);
                L[j].push_back(i);
                if(H[i] == 1)
                {
                    cost[i][j] = A[i][j];
                    cost[j][i] = -A[i][j];
                    capacity[i][j] = INF;
                }
                else
                {
                    if(H[j] == 1)
                    {
                        cost[i][j] = -A[j][i];
                        cost[j][i] = A[j][i];
                        capacity[j][i] = INF;
                    }
                }
            }
        }
    }


    while(bellmanFord())
    {
        int Fmin = INF;
        int x = destination;

        while(x > source)
        {
            Fmin = min(Fmin, capacity[ T[x] ][x] - flow[ T[x] ][x]);
            x = T[x];
        }

        x = destination;
        solution += D[destination] * Fmin;

        while(x > source)
        {
            flow[ T[x] ][x] += Fmin;
            flow[x][ T[x] ] -= Fmin;
            x = T[x];
        }
    }

    fout << solution;



    return 0;
}