#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int kMaxN = 65;
const int kInf = 0x3f3f3f3f;

int N, M, in[kMaxN], out[kMaxN];
vector<pair<int, int>> G[kMaxN];
int cap[kMaxN][kMaxN], ans;

int dist[kMaxN], padre[kMaxN];
queue<int> q;
bool in_q[kMaxN];

void Link(int x, int y, int cost, int capacity) {
    G[x].emplace_back(y, cost);
    G[y].emplace_back(x, -cost);
    cap[x][y] = capacity;
}

void BuildGraph() {
    ifstream fin("traseu.in");
    fin >> N >> M;
    while (M--) {
        int x, y, c;
        fin >> x >> y >> c;
        ++out[x];
        ++in[y];
        Link(x, y, c, kInf);
        ans += c;
    }
    for (int i = 1; i <= N; ++i)
        if (in[i] > out[i])
            Link(0, i, 0, in[i] - out[i]);
        else if (in[i] < out[i])
            Link(i, N + 1, 0, out[i] - in[i]);
}

bool BellmanFord() {
    memset(dist, kInf, sizeof dist);
    dist[0] = 0;
    q.push(0);
    in_q[0] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        in_q[node] = false;
        for (auto it : G[node])
            if (cap[node][it.first] && dist[node] + it.second < dist[it.first]) {
                dist[it.first] = dist[node] + it.second;
                padre[it.first] = node;
                if (!in_q[it.first]) {
                    q.push(it.first);
                    in_q[it.first] = true;
                }
            }
    }
    return dist[N + 1] < kInf;
}

void Solve()
{
    while (BellmanFord()) {
        int flow = kInf;
        for (int i = N + 1; i; i = padre[i])
            flow = min(flow, cap[padre[i]][i]);
        for (int i = N + 1; i; i = padre[i]) {
            cap[padre[i]][i] -= flow;
            cap[i][padre[i]] += flow;
        }
        ans += flow * dist[N + 1];
    }
}

int main()
{
    BuildGraph();
    Solve();
    ofstream("traseu.out")<<ans<<"\n";
    return 0;
}