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

using namespace std;

const int Nmax = 64, INF = 0x3f3f3f3f;

vector<int> G[Nmax];
int C[Nmax][Nmax], F[Nmax][Nmax], Father[Nmax];
int Cost[Nmax][Nmax];
int Dist[Nmax];
int DegIn[Nmax], DegOut[Nmax];

int N, TotalCost;

void Read()
{
    ifstream cin("traseu.in");

    int M;
    cin >> N >> M;

    while (M--)
    {
        int x, y, cost;
        cin >> x >> y >> cost;

        G[x].push_back(y);
        G[y].push_back(x);

        C[x][y] = INF;
        Cost[x][y] = cost;
        Cost[y][x] = -cost;

        DegOut[x]++;
        DegIn[y]++;

        TotalCost += cost;
    }

    cin.close();

    for (int i = 1; i <= N; i++)
    {
        if (DegIn[i] > DegOut[i])
        {
            G[0].push_back(i);
            G[i].push_back(0);

            C[0][i] = DegIn[i] - DegOut[i];
        }
        else if(DegOut[i] > DegIn[i])
        {

            G[i].push_back(N + 1);
            G[N + 1].push_back(i);

            C[i][N + 1] = DegOut[i] - DegIn[i];
        }
    }
}

bool BellmanFord(const int S, const int D)
{
    queue<int> Q;
    long long inQueue = (1LL << S);
    memset(Dist, INF, sizeof(Dist));

    Dist[S] = 0;
    for (Q.push(S); !Q.empty();)
    {
        const int node = Q.front();
        Q.pop();

        inQueue ^= (1LL << node);

        for (auto p: G[node])
        {
            if (C[node][p] == F[node][p]) continue;

            if (Dist[p] > Dist[node] + Cost[node][p])
            {
                Dist[p] = Dist[node] + Cost[node][p];
                Father[p] = node;

                if (!((1LL << p) & inQueue))
                {
                    inQueue |= (1LL << p);
                    Q.push(p);
                }
            }
        }
    }

    return (Dist[D] < INF);
}

pair<int, int> GetFlow(const int S, const int D)
{
    int Flow = 0, FlowCost = 0;

    while (BellmanFord(S, D))
    {
        int fmin = INF;
        for (int i = D; i != S; i = Father[i])
            fmin = min(fmin, C[Father[i]][i] - F[Father[i]][i]);

        for (int i = D; i != S; i = Father[i])
        {
            F[Father[i]][i] += fmin;
            F[i][Father[i]] -= fmin;
        }

        Flow += fmin;
        FlowCost += fmin * Dist[D];
    }

    return make_pair(Flow, FlowCost);
}

void Write(const int flowcost)
{
    ofstream cout("traseu.out");
    cout << flowcost + TotalCost << "\n";
    cout.close();
}

int main()
{
    Read();
    pair<int, int> Sol = GetFlow(0, N + 1);
    Write(Sol.second);
}