#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("traseu.in");
ofstream out("traseu.out");
const int INF = 0x3f3f3f3f;
vector<int> G[100];
int C[100][100],Cs[100][100];
int son[100],inq[100],D[100],sou,dest;
int pr[100],ans;
queue<int> q;
int N,M;
int bf(){
    for(int i=1;i<=dest;i++) D[i]=pr[i]=INF;
    D[sou]=0,q.push(sou),inq[sou]=1;
    while(!q.empty()){
        int x=q.front(); q.pop(); inq[x]=0;
        for(vector<int>::iterator it=G[x].begin();it!=G[x].end();++it){
            if(C[x][*it] && D[x]+Cs[x][*it] < D[*it]){
                D[*it]=D[x]+Cs[x][*it];
                pr[*it]=x;
                if(!inq[*it]) q.push(*it),inq[*it]=1;
            }
        }
    }
    return D[dest]<INF;
}
void addpath(){
    int p=dest,m=INF;
    while(p!=sou) m=min(m,C[pr[p]][p]),p=pr[p];
    if(!m) return;
    p=dest;
    while(p!=sou){
        C[pr[p]][p]-=m;
        ans += Cs[pr[p]][p]*m;
        C[p][pr[p]]+=m;
        p=pr[p];
    }
}
int main(){
    in>>N>>M;
    int x,y,c;
    for(int i=1;i<=M;i++){
        in>>x>>y>>c;
        G[x].push_back(y);
        G[y].push_back(x);
        Cs[x][y]=c,Cs[y][x]=-c;
        C[x][y]=INF,C[y][x]=0;
        son[x]++,son[y]--,ans+=c;
    }
    sou=N+1,dest=N+2;
    for(int i=1;i<=N;i++){
        if(son[i]!=0){
            G[sou].push_back(i);
            G[i].push_back(sou);
            G[i].push_back(dest);
            G[dest].push_back(i);
            if(son[i]<0) C[sou][i]+=-son[i];
            if(son[i]>0) C[i][dest]+=son[i];
        }
    }
    while(bf()) addpath();
    out<<ans<<'\n';
    return 0;
}