#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
#include <iostream>
using namespace std;
#define FOR(i,a,b) for (i=a;i<=b;i++)
#define fori(it,v) for (it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
ifstream in("traseu.in");
ofstream out("traseu.out");
vector<int> dist(300),ver(300);
vector<vector<int> > a(300);
queue<int> q;
int d[300][300],pred[305],cap[300][300],nr_in[300],nr_out[300],n,cost;
int flux()
{
	int nod,creste;
	q.push(0);
	vector<int>::iterator it;
	pred[n+1]=0;
	fill(all(dist),1<<30);
	dist[0]=0;
	while (!q.empty())
	{
		nod=q.front();
		fori(it,a[nod])
			if (cap[nod][*it]&&dist[nod]+d[nod][*it]<dist[*it])
			{
				dist[*it]=dist[nod]+d[nod][*it];
				pred[*it]=nod;
				if(!ver[*it])
				{
					ver[*it]=1;
//					cout<<"Baga: "<<*it<<'\n';
					q.push(*it);
				}

			}
		q.pop();
		ver[nod]=0;
	}
//	FOR(nod,0,n+1)
//		cout<<pred[nod]<<' ';
//	//cout<<'\n';
	if (!pred[n+1])
		return 0;
	nod=n+1;
	creste=1<<30;
	while (nod)
	{
		creste=min(creste,cap[pred[nod]][nod]);
		nod=pred[nod];
	}
	nod=n+1;
//	cout<<dist[n+1]*creste<<"----\n";
	cost+=dist[n+1]*creste;
	while (nod)
	{
		if(pred[nod]==0||nod==n+1)
		{
			cap[pred[nod]][nod]-=creste;
			cap[nod][pred[nod]]+=creste;
		}
		nod=pred[nod];
	}
	return 1;

}
int main()
{
	int i,j,m,x,y,z;
	in>>n>>m;
	FOR(i,1,m)
	{
		in>>x>>y>>z;
		d[x][y]=z;
		//d[y][x]=-z;
		cap[x][y]=1<<30;
		nr_in[y]++;
		nr_out[x]++;
		a[x].pb(y);
		cost+=z;
	}
	FOR(i,1,n)
	{
		if(nr_in[i]>nr_out[i])
		{
			a[0].pb(i);
			cap[0][i]=nr_in[i]-nr_out[i];
		}
		else
		{
			a[i].pb(n+1);
			cap[i][n+1]=nr_out[i]-nr_in[i];
		}
	}
	vector<int>::iterator it;
//	fori(it,a[4])
///		cout<<*it<<'\n';
//	cout<<'\n';
	while (flux());
	out<<cost<<'\n';
	in.close();
	out.close();
	return 0;
}