#include <cstdio>
#include <vector>
#include <queue>
#define inf 1<<28
#define N 65
using namespace std;

struct edge{
            int to,cost;
           };
vector <edge> G[N];
bool viz[N];
int gr[N],t[N],dist[N],c[N][N],n,sol;

void Read(){

    int i,m,x,y,cost;
    edge e;
    freopen("traseu.in","r",stdin);

    scanf("%d%d",&n,&m);
    while (m--){
        scanf("%d%d%d",&x,&y,&cost);
        gr[x]++;gr[y]--;c[x][y]=inf;sol+=cost;

        e.to=y;e.cost=cost;G[x].push_back(e);

        e.to=x;e.cost=-cost;G[y].push_back(e);

        }
}

void BuildGraph(){

    int i;edge e;

    for (i=1;i<=n;++i)
        {
        if (gr[i]<0) {
                      e.to=i;e.cost=0;
                      G[0].push_back(e);
                      c[0][i]=-gr[i];
                     }
        if (gr[i]>0) {
                      e.to=n+1;e.cost=0;
                      G[i].push_back(e);
                      c[i][n+1]=gr[i];
                     }
        }
}

int BellmanFord(){

    queue <int> Q;
    int i,node,flow;
    vector <edge>::iterator it;
    edge e;

    for (i=0;i<=n+1;++i)
        {
        dist[i]=inf;
        t[i]=-1;
        viz[i]=0;
        }
    dist[0]=0;viz[0]=1;Q.push(0);

    while (!Q.empty())
        {
        node=Q.front();Q.pop();

        for (it=G[node].begin();it!=G[node].end();++it)
            if (c[node][(*it).to] && dist[(*it).to]>dist[node]+(*it).cost)
                {
                dist[(*it).to]=dist[node]+(*it).cost;
                t[(*it).to]=node;

                if (!viz[(*it).to]) {
                                    Q.push((*it).to);
                                    viz[(*it).to]=1;
                                    }
                }
        viz[node]=0;
        }

    if (dist[n+1]<inf)
        {
        flow=inf;

        for (i=n+1;i;i=t[i])
            flow=min(flow,c[t[i]][i]);

        for (i=n+1;i;i=t[i])
            {
            c[t[i]][i]-=flow;
            c[i][t[i]]+=flow;
            }
        return flow*dist[n+1];
        }
    return 0;
}

void Solve(){

    int flow=1;

    while (flow)
        {
        flow=BellmanFord();
        sol+=flow;
        }
}

void Write(){

    freopen("traseu.out","w",stdout);

    printf("%d",sol);
}
int main()
{
    Read();
    BuildGraph();
    Solve();
    Write();
    return 0;
}