#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define zero(a) memset(a,0,sizeof(a))
#define N 200
#define M 100
#define x first
#define y second
const int oo=(int)1e4;
typedef pair<int,int>pii;
int n,m,a,b,c,sum,flow[N][N],cost[N][N],out[M],in[M],sink,d[N],p[N];

struct cf{
	bool operator()(const pii &a,const pii &b)const{
		return (a.y>b.y);
	};
};

void open(){
	freopen("traseu.in","r",stdin);
	freopen("traseu.out","w",stdout);
}

void input(){
	sum=0;
	scanf("%d%d",&n,&m);
	zero(cost);zero(in);zero(out);zero(flow);
	REP(i,m){
		scanf("%d%d%d",&a,&b,&c);
		flow[a][b]=oo;
		cost[a][b]=c;
		cost[b][a]=-c;
		sum+=c;
		out[a]++;in[b]++;
	}
	sink=n+1;
	REP(i,n){
		if (in[i+1]==out[i+1]) continue;
		if (in[i+1]>out[i+1]){
			flow[0][i+1]=in[i+1]-out[i+1];
		}
		else {
			flow[i+1][sink]=out[i+1]-in[i+1];
		}
	}
}

bool dijkstra(){
	REP(i,sink+1) d[i]=oo;
	memset(p,-1,sizeof(p));
	priority_queue<pii,vector<pii>,cf >pq;
	d[0]=0;
	pq.push(pii(0,0));
	while (!pq.empty()){
		pii top=pq.top();
		pq.pop();
		int vx=top.x;
		int dx=top.y;
		if (dx<=d[vx]){
			REP(i,sink+1){
				if (flow[vx][i]<=0) continue;
				if (d[i]>d[vx]+cost[vx][i]){
					d[i]=d[vx]+cost[vx][i];
					p[i]=vx;
					pq.push(pii(i,d[i]));
				}
			}
		}
	}
	return d[sink]!=oo;
}

int mincost(){
	int ctot=0;
	while (1){
		if (!dijkstra()) break;
		int now,tmp,cap;
		cap=oo;
		now=sink;
		while (p[now]!=-1){
			tmp=p[now];
			cap=min(cap,flow[tmp][now]);
			now=tmp;
		}
		now=sink;
		while (p[now]!=-1){
			tmp=p[now];
			flow[tmp][now]-=cap;
			flow[now][tmp]+=cap;
			now=tmp;
		}
		ctot+=cap*d[sink];
	}
	return ctot;
}

void solve(){
	printf("%d\n",sum+mincost());
}

int main(){
	open();
	input();
	solve();
	//system("pause");
	return 0;
}