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

using namespace std;

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

const int MAXN = 62;
const int INF = 1000000002;

int N, M, A, B, C, Source, Dest;
vector<int> v[MAXN];
int capacity[MAXN][MAXN], cost[MAXN][MAXN];
int in_deg[MAXN], out_deg[MAXN];
int dist[MAXN], dist_source[MAXN];
int q[MAXN * MAXN], back;
int ans;

bool flow_step() {
    dist[Source] = 0;
    for (int i = 1; i <= N + 1; ++i) {
        dist[i] = INF;
    }
    back = 1;
    q[1] = Source;
    for (int front = 1; front <= back; ++front) {
        int node = q[front];
        for (const int& neigh : v[node]) {
            if (capacity[node][neigh] && dist[neigh] > dist[node] + cost[node][neigh]) {
                dist[neigh] = dist[node] + cost[node][neigh];
                dist_source[neigh] = node;
                q[++back] = neigh;
            }
        }
    }

    if (dist[Dest] == INF) return false;

    int current_flow = INF;
    for (int node = Dest; node != Source; node = dist_source[node]) {
        current_flow = min(current_flow, capacity[dist_source[node]][node]);
    }
    
    ans += current_flow * dist[Dest];
    for (int node = Dest; node != Source; node = dist_source[node]) {
        capacity[dist_source[node]][node] -= current_flow;
        capacity[node][dist_source[node]] += current_flow;
    }

    return true;
}
int main()
{
    fin >> N >> M;
    for (int i = 0; i < M; ++i) {
        fin >> A >> B >> C;
        v[A].push_back(B);
        v[B].push_back(A);
        capacity[A][B] = INF;
        capacity[B][A] = 0;
        cost[A][B] = C;
        cost[B][A] = -C;
        in_deg[B]++;
        out_deg[A]++;
        ans += C;
    }

    Source = 0; Dest = N + 1;
    for (int i = 1; i <= N; ++i) {
        if (in_deg[i] > out_deg[i]) {
            capacity[Source][i] = in_deg[i] - out_deg[i];
            v[Source].push_back(i);
            v[i].push_back(Source);
        } else if (in_deg[i] < out_deg[i]) {
            capacity[i][Dest] = out_deg[i] - in_deg[i];
            v[i].push_back(Dest);
            v[Dest].push_back(i);
        }
    }

    while (flow_step());

    fout << ans;

    return 0;
}