#include <bits/stdc++.h>

using namespace std;

const int Nmax=69;
const int inf=1e9;

int n, m;
vector <int> g[Nmax];
int ind[Nmax], outd[Nmax];

int cap[Nmax][Nmax], cost[Nmax][Nmax], flow[Nmax][Nmax];
int costTo[Nmax], flowTo[Nmax], bef[Nmax];

bool omul_clopot()
{
    for (int i=0; i<=n+1; ++i)
    {
        costTo[i]=inf;
        flowTo[i]=inf;
    }
    queue <int> q;
    q.push(0);
    costTo[0]=0;
    long long int inq=(1<<0);
    while(!q.empty())
    {
        int node=q.front();
        q.pop();
        inq^=(1LL<<node);
        for(auto it : g[node])
        {
            if(flow[node][it]<cap[node][it])
            {
                if(costTo[it]>costTo[node]+cost[node][it])
                {
                    costTo[it]=costTo[node]+cost[node][it];
                    flowTo[it]=min(flowTo[node],cap[node][it]-flow[node][it]);
                    bef[it]=node;
                    if(inq&(1LL<<it))
                    {
                        continue;
                    }
                    q.push(it);
                    inq|=(1LL<<it);
                }
            }
        }
    }
    return (costTo[n+1] != inf);
}

long long int flux()
{
    long long int minCost=0;
    while(omul_clopot())
    {
        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()
{
    ifstream fin("traseu.in");
    ofstream fout("traseu.out");
    fin>>n>>m;
    int costt=0;
    for (int i=1; i<=m; ++i)
    {
        int u,v,z;
        fin>>u>>v>>z;
        outd[u]++;
        ind[v]++;
        g[u].push_back(v);
        g[v].push_back(u);
        cost[u][v]=z;
        cost[v][u]=-z;
        cap[u][v]=inf;
        costt+=z;
    }
    for (int i=1; i<=n; ++i)
    {
        if(ind[i]>outd[i])
        {
            g[0].push_back(i);
            g[i].push_back(0);
            cap[0][i]=ind[i]-outd[i];
        }
        else if(ind[i]<outd[i])
        {
            g[i].push_back(n+1);
            g[n+1].push_back(i);
            cap[i][n+1]=outd[i]-ind[i];
        }
    }
    fout<<costt+flux()<<"\n";
    return 0;
}