#include <bits/stdc++.h>

using namespace std;

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

const int inf = 1e9, Nmax = 66;

int cost[Nmax][Nmax], i, n, m, x, y, cc, j, grd[Nmax], ans;
vector<int> positive, negative;


void find_all_dists()
{
    int i, j, k;
    for(k=1; k<=n; ++k)
        for(i=1; i<=n; ++i)
            for(j=1; j<=n; ++j)
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
}

class MyGraph
{
    vector<int> v[Nmax];
    int t[Nmax], d[Nmax], c[Nmax][Nmax], cost[Nmax][Nmax];
    bool inQueue[Nmax];

    bool bellman()
    {
        queue<int> q;
        memset(inQueue, 0, sizeof(inQueue));
        for(int i=1; i<=n+1; ++i) d[i] = inf;

        d[0] = 0;
        t[0] = 1;
        q.push(0);
        inQueue[0] = 1;

        while(!q.empty())
        {
            int node = q.front();
            q.pop();
            inQueue[node] = 0;

            for(auto it : v[node])
                if(c[node][it] && d[it] > d[node] + cost[node][it])
                {
                    d[it] = d[node] + cost[node][it];
                    t[it] = node;

                    if(!inQueue[it])
                    {
                        inQueue[it] = 1;
                        q.push(it);
                    }
                }
        }

        return (d[n+1] != inf);
    }

    public:
        int maxFlow_minCost()
        {
            int node, dad, Cost = 0, add;
            while(bellman())
            {
                node = n+1;
                add = inf;
                while(node)
                {
                    dad = t[node];
                    add = min(add, c[dad][node]);
                    node = dad;
                }

                node = n+1;
                while(node)
                {
                    dad = t[node];
                    c[dad][node] -= add;
                    c[node][dad] += add;
                    Cost += add * cost[dad][node];
                    node = dad;
                }
            }

            return Cost;
        }

        void add_edge(int x, int y, int cap, int cc)
        {
            v[x].push_back(y); v[y].push_back(x);
            c[x][y] = cap; c[y][x] = 0;
            cost[x][y] = cc; cost[y][x] = -cc;
        }
} graph;

int main()
{
    fin >> n >> m;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
            cost[i][j] = (i == j ? 0 : inf);

    for(i=1; i<=m; ++i)
    {
        fin >> x >> y >> cc;
        grd[x]++; grd[y]--;
        cost[x][y] = cc;
        ans += cc;
    }

    find_all_dists();

    for(i=1; i<=n; ++i)
        if(grd[i] < 0) positive.push_back(i);
            else if(grd[i] > 0) negative.push_back(i);

    for(auto it : positive) graph.add_edge(0, it, -grd[it], 0);
    for(auto it : negative) graph.add_edge(it, n+1, grd[it], 0);

    for(auto x : positive)
        for(auto y : negative)
            graph.add_edge(x, y, inf, cost[x][y]);

    fout << ans + graph.maxFlow_minCost() << '\n';
    return 0;
}