#include <bits/stdc++.h>
	
using namespace std;
	
const string FILENAME = "traseu";	
ifstream fin(FILENAME + ".in");
ofstream fout(FILENAME + ".out");
	
const int NMax = 80;
const int INF = INT_MAX / 8;

int cost[NMax][NMax];
pair < int, int > grad[NMax];

struct Flow {
    int n, source, dest;
    vector < vector < pair < int, int > > > G;
    vector < int > parent, costParent;
    vector < vector < int > > cap;

    Flow(int n): n(n), G(n), costParent(n) {
        source = n - 2;
        dest = n - 1;
        cap.assign(n, vector < int > (n, 0));
    }

    void Add(int a, int b, int size, int price) {
        G[a].push_back({b, price});
        G[b].push_back({a, -price});
        cap[a][b] += size;
    }

    bool Bellman() {
        parent.assign(n, -1);
        vector < int > dist(n, INF), inque(n, 0);
        dist[source] = 0;
        inque[source] = 1;

        queue < int > q;
        q.push(source);
        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (auto x : G[node]) {
                if (cap[node][x.first] && dist[node] + x.second < dist[x.first]) {
                    dist[x.first] = dist[node] + x.second;
                    if (!inque[x.first]) {
                        q.push(x.first);
                        inque[x.first] = 1;
                    }
                    parent[x.first] = node;
                    costParent[x.first] = x.second;
                }
            }
            inque[node] = 0;
        }

        return parent[dest] != -1;
    }

    pair < int, int > Maxflow() {
        int totalFlow = 0;
        int totalCost = 0;

        while (Bellman()) {
            int flow = INF;
            int cost = 0;
            for (int now = dest; now != source; now = parent[now]) {
                flow = min(flow, cap[parent[now]][now]);
                cost += costParent[now];
            }
            for (int now = dest; now != source; now = parent[now]) {
                int prev = parent[now];
                cap[prev][now] -= flow;
                cap[now][prev] += flow;
            }
            totalFlow += flow;
            totalCost += flow * cost;
        }

        return {totalFlow, totalCost};
    }
};

int main() {
    int n, m;
    fin >> n >> m;

    int sum = 0;
    Flow flow(n + 2);
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        --x; --y;
        ++grad[x].second;
        ++grad[y].first;
        flow.Add(x, y, INF, c);
        sum += c;
    }
    for (int i = 0; i < n; ++i) {
        if (grad[i].second < grad[i].first) {
            int dif = grad[i].first - grad[i].second;
            flow.Add(flow.source, i, dif, 0);
        }
        if (grad[i].first < grad[i].second) {
            int dif = grad[i].second - grad[i].first;
            flow.Add(i, flow.dest, dif, 0);
        }
    }

    fout << flow.Maxflow().second + sum;
    return 0;
}