#include <cstdio>
#include <vector>

#define pb push_back

#define INF 1000000000

#define MAXN 60
#define MAXK (2*MAXN+2)
#define MASK 127

std::vector <int> v[MAXK+1];
int s, d, q[MASK+1], gr[MAXN+1], from[MAXK+1], dist[MAXK+1];
int f[MAXK+1][MAXK+1], c[MAXK+1][MAXK+1], cost[MAXK+1][MAXK+1];
int e[MAXN+1][MAXN+1];
bool ok[MAXK+1];

inline void graf(int n){
    s=0;
    d=2*n+1;
    for(int i=1; i<=n; i++){
        v[s].pb(i);
        v[i].pb(s);
        if(gr[i]>0) c[s][i]=gr[i];
        v[i].pb(i+n);
        v[i+n].pb(i);
        c[i][i+n]=INF;
        v[i+n].pb(d);
        v[d].pb(i+n);
        if(gr[i]<0) c[i+n][d]=-gr[i];
        for(int j=1; j<=n; j++){
            if(e[i][j]){
                v[i+n].pb(j);
                v[j].pb(i+n);
                c[i+n][j]=INF;
                cost[i+n][j]=e[i][j];
                cost[j][i+n]=-e[i][j];
            }
        }
    }
}

inline bool bellman(){
    int st=0, dr=0, x;
    for(int i=s; i<=d; i++)
        dist[i]=INF;
    dist[s]=0;
    q[dr++]=s;
    ok[s]=1;
    while(st<dr){
        x=q[st&MASK];
        st++;
        ok[x]=0;
        for(auto y:v[x]){
            if((c[x][y]>f[x][y])&&(dist[x]+cost[x][y]<dist[y])){
                dist[y]=dist[x]+cost[x][y];
                from[y]=x;
                if(!ok[y]){
                    ok[y]=1;
                    q[dr&MASK]=y;
                    dr++;
                }
            }
        }
    }
    return (dist[d]<INF);
}

inline int flux(){
    int a, x, ans=0;
    while(bellman()){
        x=d;
        a=INF;
        while(x!=s){
            if(c[from[x]][x]-f[from[x]][x]<a)
                a=c[from[x]][x]-f[from[x]][x];
            x=from[x];
        }
        x=d;
        while(x!=s){
            f[from[x]][x]+=a;
            f[x][from[x]]-=a;
            x=from[x];
        }
        ans+=a*dist[d];
    }
    return ans;
}

int main(){
    FILE *fin, *fout;
    fin=fopen("traseu.in", "r");
    fout=fopen("traseu.out", "w");

    int n, m, x, y, z, sum=0;
    fscanf(fin, "%d%d", &n, &m);
    for(int i=0; i<m; i++){
        fscanf(fin, "%d%d%d", &x, &y, &z);
        e[y][x]=z;
        gr[x]++;
        gr[y]--;
        sum+=z;
    }

    graf(n);

    fprintf(fout, "%d\n", flux()+sum);

    fclose(fin);
    fclose(fout);
    return 0;
}