#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("traseu.in");
ofstream fout("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(){
fin>>N>>M;
int x,y,c;
for(int i=1;i<=M;i++){
fin>>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();
fout<<ans<<'\n';
return 0;
}