#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MaxN 200
#define INF 2000000000
 
using namespace std;
 
FILE *IN,*OUT;

int N,M,cnt[MaxN],L[MaxN][MaxN],X,Y,C,Sum=0,cap[MaxN][MaxN],flow[MaxN][MaxN],D[MaxN],father[MaxN];
vector <pair<int,int>> Graph[MaxN];
queue <int> Q;
void Bipartite_Graph()
{
	for(int i=1;i<=N;i++)
	{
		Graph[i].push_back(make_pair(0,0));
		Graph[0].push_back(make_pair(i,0));
		Graph[i+N].push_back(make_pair(2*N+1,0));
		Graph[2*N+1].push_back(make_pair(i+N,0));
		Graph[i].push_back(make_pair(i+N,0));
		Graph[i+N].push_back(make_pair(i,0));
		cap[i][i+N]=INF;
		if(cnt[i]>0)
			cap[0][i]=cnt[i];
		if(cnt[i]<0)
			cap[i+N][2*N+1]=-cnt[i];
		for(int j=1;j<=N;j++)
			if(L[j][i])
			{
				Graph[i+N].push_back(make_pair(j,L[j][i]));
				Graph[j].push_back(make_pair(i+N,-L[j][i]));
				cap[i+N][j]=INF;
			}
	}
}
bool Bellman_Ford(int start,int end)
{
	int x,y,z;
	memset(father,0,sizeof father);
	for(int i=0;i<=2*N+1;i++)
		D[i]=INF;
	D[start]=0;
	Q.push(start);
	while(!Q.empty())
	{
		x=Q.front();
		for(int i=0;i<Graph[x].size();i++)
		{
			y=Graph[x][i].first;
			z=Graph[x][i].second;
			if(D[y]>D[x]+z&&cap[x][y]>flow[x][y])
				D[y]=D[x]+z,Q.push(y),father[y]=x;
		}
		Q.pop();
	}
	if(D[end]!=INF)
		return true;
	else return false;
}
int Flow(int start,int end)
{
	int F=0,Min;
	while(Bellman_Ford(start,end))
	{
		Min=INF;
		for(int i=end;i!=start;i=father[i])
			Min=min(Min,cap[father[i]][i]-flow[father[i]][i]);
		for(int i=end;i!=start;i=father[i])
			flow[father[i]][i]+=Min,flow[i][father[i]]-=Min;
		F+=Min*D[end];
	}
	return F;
}
int main()
{
    IN=fopen("traseu.in","r");
    OUT=fopen("traseu.out","w");
    
	fscanf(IN,"%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		fscanf(IN,"%d%d%d",&X,&Y,&C);
			cnt[X]++;
			cnt[Y]--;
			L[X][Y]=C;
			Sum+=C;
	}
	Bipartite_Graph();
	fprintf(OUT,"%d",Flow(0,2*N+1)+Sum);
    return 0;
}