#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int NMAX = 60;
const int INF = 1e9;

int N, M;
vector <int> g[NMAX + 5];
int inDeg[NMAX + 5], outDeg[NMAX + 5];

int capacity[NMAX + 5][NMAX + 5], cost[NMAX + 5][NMAX + 5], flow[NMAX + 5][NMAX + 5];
int costTo[NMAX + 5], flowTo[NMAX + 5], bef[NMAX + 5];

bool Bellman()
{
    for(int i = 0; i <= N + 1; i++)
        costTo[i] = flowTo[i] = INF;

    queue <int> Q;
    Q.push(0); costTo[0] = 0;
    int inQ = 1 << 0;

    while(!Q.empty())
    {
        int node = Q.front();
        Q.pop();
        inQ ^= (1 << node);

        for(auto it : g[node])
            if(flow[node][it] < capacity[node][it])
                if(costTo[it] > costTo[node] + cost[node][it])
                {
                    costTo[it] = costTo[node] + cost[node][it];
                    flowTo[it] = min(flowTo[node], capacity[node][it] - flow[node][it]);

                    bef[it] = node;

                    if(it == N + 1)
                        continue;

                    if(inQ & (1 << it))
                        continue;

                    Q.push(it);
                    inQ |= (1 << it);
                }
    }

    return (costTo[N + 1] != INF);
}

long long GetMinCostMaxFlow()
{
    long long minCost = 0;

    while(Bellman())
    {
        for(int node = N + 1; node != 0; node = bef[node])
        {
            flow[bef[node]][node] += flowTo[N + 1];
            flow[node][bef[node]] -= flowTo[N + 1];
        }

        minCost += 1LL * flowTo[N + 1] * costTo[N + 1];
    }

    return minCost;
}

int main()
{
    fin >> N >> M;

    int totalEdgeCost = 0;
    for(int i = 1; i <= M; i++)
    {
        int x, y, z;
        fin >> x >> y >> z;

        outDeg[x]++;
        inDeg[y]++;

        g[x].push_back(y);
        g[y].push_back(x);

        cost[x][y] = z;
        capacity[x][y] = INF;

        totalEdgeCost += z;
    }

    for(int i = 1; i <= N; i++)
        if(inDeg[i] > outDeg[i])
        {
            g[0].push_back(i);
            g[i].push_back(0);

            capacity[0][i] = inDeg[i] - outDeg[i];
        }
        else if(inDeg[i] < outDeg[i])
        {
            g[i].push_back(N + 1);
            g[N + 1].push_back(i);

            capacity[i][N + 1] = outDeg[i] - inDeg[i];
        }

    fout << totalEdgeCost + GetMinCostMaxFlow() << '\n';

    return 0;
}