#include <cstdlib>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

#include <fstream>

#include <iostream>

#define rep(i, l, r) for(int i=l; i<=r; i++)

#define clr(x, c) memset(x, c, sizeof(x))

#define N 123

#define MAX 1<<30

#define ll long long

using namespace std;

int read()

{

	int x=0, f=1; char ch=getchar();

	while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }

	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }

	return x*f;

}

int n, m, l[N], st[N], lx[N], ly[N], v[N][N];

bool vx[N], vy[N];

bool Find(int x)

{

	vx[x]=1;

	rep(y, 1, n) if (!vy[y])

	{

		int a=lx[x]+ly[y]-v[x][y];

		if (!a)

		{

			vy[y]=1; if (!l[y] || Find(l[y])) { l[y]=x; return true; }

		}

		else st[y]=min(st[y], a);

	}

	return false;

}

int km()

{

	rep(i, 1, n) lx[i]=-MAX; clr(ly, 0); clr(l, 0);

	rep(i, 1, n) rep(j, 1, n) if (lx[i]<v[i][j]) lx[i]=v[i][j];

	rep(i, 1, n)

	{

		rep(j, 1, n) st[j]=MAX;

		while (1)

		{

			clr(vx, 0); clr(vy, 0);

			if (Find(i)) break; int a=MAX;

			rep(j, 1, n) if (!vy[j] && st[j]<a) a=st[j];

			rep(j, 1, n) if (vx[j]) lx[j]-=a;

			rep(j, 1, n) if (vy[j]) ly[j]+=a; else st[j]-=a;

		}

	}

	int ans=0;

	rep(i, 1, n) if (!l[i] || v[l[i]][i]==-MAX) return -1; else ans+=v[l[i]][i];

	return -ans;

}

int main()

{

	while (~scanf("%d%d", &n, &m))

	{

		rep(i, 1, n) rep(j, 1, n) v[i][j]=MAX;

		rep(i, 1, m) { int x=read(), y=read(), z=read(); if (v[x][y]>z) v[x][y]=z; }

		rep(i, 1, n) rep(j, 1, n) v[i][j]*=-1;

		printf("%d\n", km());

	}

	return 0;

}