using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <algorithm>

#define pb push_back
#define sz size
#define f first
#define s second
#define II inline
#define ll long long
#define db double
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define all(v) v.begin() , v.end()
#define CC(v) memset((v),0,sizeof((v)))
#define CP(v,w) memcpy((v),(w),sizeof((w)))
#define mp make_pair

#define IN  "traseu.in"
#define OUT "traseu.out"
#define N_MAX 1<<6

typedef vector<int> VI;
typedef pair<int,int> pi;
typedef vector<string> VS;

int rez,N,M,S,D;
int T[N_MAX],G[N_MAX],Dist[N_MAX],C[N_MAX][N_MAX],P[N_MAX][N_MAX];
VI A[N_MAX];

II void scan()
{
	freopen(IN,"r",stdin);
	freopen(OUT,"w",stdout);
	
	int x,y,p;
	scanf("%d%d",&N,&M);
	FOR(i,1,M)
	{
		scanf("%d%d%d",&x,&y,&p);
		++G[x],--G[y];
		P[x][y] = p;
		rez += p;
	}	
}

struct comp{ bool operator() (int i,int j) {return Dist[i] > Dist[j];} };
priority_queue<int,VI,comp> Q;

II void Dijkastra(int S)
{
	vector<bool> viz(N_MAX,0);
	memset(Dist,100,sizeof(Dist));
	
	Dist[S] = 0;
	Q.push(S);
	
	for(int nod;!Q.empty();)
	{
		nod = Q.top();
		Q.pop();
		viz[nod] = false;
		
		for(VI::iterator it=A[nod].begin();it != A[nod].end();++it)
		if(C[nod][*it] && Dist[*it] > Dist[nod] + P[nod][*it])
			{
				Dist[*it] = Dist[nod] + P[nod][*it];
				T[*it] = nod;
				
				if(!viz[*it])
					viz[*it] = true,Q.push(*it);
			}	
	}	
	
	FOR(i,1,D)
		P[S][i] = Dist[i];
}

II void solve()
{
	int total(0);
	S = N+1;
	D = N+2;
	
	FOR(i,1,N)
	{
		if(G[i] < 0)
			A[S].pb(i),
			A[i].pb(S),
			C[S][i] =  -G[i];
		if(G[i] > 0)
			A[D].pb(i),
			A[i].pb(D),
			C[i][D] = G[i],total += G[i];
	}

	for(VI::iterator i=A[S].begin();i != A[S].end();++i)
	for(VI::iterator j=A[D].begin();j != A[D].end();++j)
		A[*i].pb(*j),A[*j].pb(*i),C[*i][*j] = N;
	
	for(VI::iterator i=A[S].begin();i != A[S].end();Dijkastra(*i),++i);
	for(VI::iterator i=A[S].begin();i != A[S].end();++i)
	for(VI::iterator j=A[D].begin();j != A[D].end();++j)
		P[*j][*i] = -P[*i][*j];
	
	for(;total;Dijkastra(S))
	{
		int fc(total);
		for(int nod = D;T[nod];fc = min(C[ T[nod] ][nod],fc),nod = T[nod]);
		for(int nod = D;T[nod];C[ T[nod] ][nod] -= fc,C[nod][ T[nod] ] += fc,nod = T[nod]);
		
		rez += Dist[D] * fc;
		total -= fc;
	}	
	
	printf("%d\n",rez);
}

int main()
{
	scan();
	solve();
	
	return 0;
}