#include <bits/stdc++.h>

#define int_pair std::pair <int, int>

#define MAXN 65
#define inf  1000000005

int N, M, Ans;
int Capacity[MAXN][MAXN],
    Cost[MAXN][MAXN],
    Grad[MAXN];
std::vector <int> ADC[MAXN];

inline void AddEdge(int x, int y, int w) {
    ADC[x].push_back(y);
    ADC[y].push_back(x);

    Capacity[x][y] = N;
    Cost[x][y] = w;
    Cost[y][x] = -w;
    -- Grad[x];
    ++ Grad[y];

    Ans += w;
}

std::ifstream In("traseu.in");
std::ofstream Out("traseu.out");

std::priority_queue <int_pair, std::vector <int_pair>, std::greater <int_pair>> PQ;
int Dist[MAXN], Parent[MAXN];

bool Dijkstra() {
    for (int i=0; i<=N+1; ++i)
        Dist[i] = inf, Parent[i] = i;
    Dist[0] = 0;
    PQ.push({0, 0});

    int_pair Top;
    while (!PQ.empty()) {
        Top = PQ.top();
        PQ.pop();

        if (Top.first > Dist[Top.second]) continue;
        for (auto Vecin:ADC[Top.second])
            if (Capacity[Top.second][Vecin] && Dist[Vecin] > Top.first + Cost[Top.second][Vecin]) {
                Dist[Vecin] = Top.first + Cost[Top.second][Vecin];
                Parent[Vecin] = Top.second;
                PQ.push({Dist[Vecin], Vecin});
            }
    }   return (Dist[N+1] != inf);
}

void Flux() {
    int Quantity, p;
    while (Dijkstra()) {
        Quantity = inf;

        p = N+1;
        while (Parent[p] != p)
            Quantity = std::min(Quantity, Capacity[Parent[p]][p]),
            p = Parent[p];

        p = N+1;
        while (Parent[p] != p)
            Capacity[Parent[p]][p] -= Quantity,
            Capacity[p][Parent[p]] += Quantity,
            p = Parent[p];

        Ans += Quantity * Dist[N+1];
    }
}

void Citire() {
    In >> N >> M;
    for (int i=0, x, y, w; i<M; ++i)
        In >> x >> y >> w, AddEdge(x, y, w);

    for (int i=1; i<=N; ++i) {
        if (Grad[i] > 0)
            ADC[0].push_back(i),
            Capacity[0][i] = Grad[i];
        else if (Grad[i] < 0)
            ADC[i].push_back(N+1),
            Capacity[i][N+1] = -Grad[i];
    }
}

void Rezolvare() {
    Flux();
    Out << Ans << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}