#include <cstdio>
#include <bitset>
#include <deque>
#include <vector>
#define DIM 65
#define INF 2000000000
using namespace std;
struct gr{
    int in;
    int ies;
};
gr grad[DIM];
int n,s,d;
int a[DIM][DIM],p[DIM][DIM],dist[DIM],tt[DIM],c[DIM][DIM],fl[DIM][DIM],cst[DIM][DIM];
int vs[DIM],vd[DIM];
vector <int> v[DIM];
bitset <DIM> f;
deque <int> dq;
void royfloyd (){ /// p = matricea drumurilor minime
    int i,j,k;
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            if (a[i][j])
                p[i][j]=a[i][j];
            else p[i][j]=INF;
        }
    }
    for (k=1;k<=n;k++){
        for (i=1;i<=n;i++){
            for (j=1;j<=n;j++){
                if (k!=i && k!=j && i!=j && p[i][k]!=INF && p[k][j]!=INF)
                    p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
            }
        }
    }
    for (i=1;i<=n;i++){
        for (j=1;j<=n;j++){
            if (p[i][j]==INF)
                p[i][j]=0;
        }
    }
}
int bellmanford (){
    int i,nod,vecin;
    for (i=0;i<=n+1;i++){
        dist[i]=INF;
        tt[i]=0;
    }
    f.reset();
    dq.push_back(s);
    dist[s]=0;
    f[s]=1;
    while (dq.size()){
        nod=dq.front();
       // printf ("%d ",nod);
        for (i=0;i<v[nod].size();i++){
            vecin=v[nod][i];
            if (c[nod][vecin]>fl[nod][vecin] && dist[nod]+cst[nod][vecin]<dist[vecin]){
                dist[vecin]=dist[nod]+cst[nod][vecin];
                tt[vecin]=nod;
                if (!f[vecin]) {// nu e in deque
                    f[vecin]=1;
                    dq.push_back(vecin);
                }
            }
        }
        f[nod]=0;
        dq.pop_front();
    }
    if (dist[d]==INF)
        return 0; /// nu se mai poate pune flux
    return 1;
}
int main()
{
    FILE *fin=fopen ("traseu.in","r");
    FILE *fout=fopen ("traseu.out","w");
    int m,i,j,sol,x,y,z,e1,e2,vecin,nod,mini;
    fscanf (fin,"%d%d",&n,&m);
    sol=0;
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d%d",&x,&y,&z);
        a[x][y]=z;
        grad[x].ies++;
        grad[y].in++;
        sol+=z;
    }
    royfloyd ();
    s=0;
    d=n+1;
    e1=e2=0;
    for (i=1;i<=n;i++){
        if (grad[i].in>grad[i].ies){
            v[s].push_back(i);
            vs[++e1]=i;
            c[s][i]=grad[i].in-grad[i].ies;
            cst[s][i]=cst[i][s]=0;
        }
        else if (grad[i].in<grad[i].ies){
            vd[++e2]=i;
            v[i].push_back(d);
            c[i][d]=grad[i].ies-grad[i].in;
            cst[d][i]=cst[i][d]=0;
        }
    }
    for (i=1;i<=e1;i++){
        for (j=1;j<=e2;j++){
            v[vs[i]].push_back(vd[j]);
            c[vs[i]][vd[j]]=1000000;
            cst[vs[i]][vd[j]]=p[vs[i]][vd[j]];
            cst[vd[j]][vs[i]]=-p[vs[i]][vd[j]];
        }
    }
    /// am construit graful pt a vedea ce muchii se repeta
    /// acum fac fmcm
    while (bellmanford()){ /// cat timp mai introduc flux
        vecin=d;
        nod=tt[d];
        mini=INF;
        while (nod){
            mini=min(mini,c[nod][vecin]-fl[nod][vecin]);
            vecin=nod;
            nod=tt[nod];
        }
        vecin=d;
        nod=tt[d];
        while (nod){
            fl[nod][vecin]+=mini;
            fl[vecin][nod]-=mini;
            vecin=nod;
            nod=tt[nod];
        }
        sol+= dist[d]*mini;
    }
    fprintf (fout,"%d",sol);
    return 0;
}