#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>

using namespace std;

int n,m,x,y,z,ans;
struct KM
{
	bool flag;
	int mat[50][50];
	int mat1[50],mat2[50];
	int s[50],t[50],l1[50],l2[50];
	void init()
	{
		memset(mat,(flag^1)<<7,sizeof(mat));
		memset(l1,0x80,sizeof(l1));
		memset(l2,0,sizeof(l2));
		memset(mat1,-1,sizeof(mat1));
		memset(mat2,-1,sizeof(mat2));
	}
	void insert(int x,int y,int w)
	{
		mat[x][y] = w;
	}
	int km(int m,int n)
	{
		int p,q,ret = 0;
		int i,j,k;
		for (i = 1;i <= m;i++)
			for (j = 1;j <= n;j++)
			l1[i] = max(mat[i][j],l1[i]);
		for (i = 1;i <= m;i++)
		{
			memset(t,255,sizeof(t));
			p = q = 0;
			for (s[0] = i;p <= q && mat1[i] < 0;p++)
			{
				k = s[p];
				for (j = 1;j <= n && mat1[i] < 0;j++)
					if (l1[k] + l2[j] == mat[k][j] && t[j] < 0)
					{
						s[++q] = mat2[j];
						t[j] = k;
						if (s[q] >= 0) continue;
						for (p = j;p >= 0;j = p)
						{
							mat2[j] = k = t[j];
							p = mat1[k];
							mat1[k] = j;
						}
					}
			}
			if (mat1[i] < 0)
			{
				i--;
				p = 0x7f7f7f7f;
				for (k = 0;k <= q;k++)
					for (j = 1;j <= n;j++)
						if (t[j] < 0 && l1[s[k]] + l2[j] - mat[s[k]][j] < p)
						p = l1[s[k]] + l2[j] - mat[s[k]][j];
			}
			for (j = 1;j <= n;j++)
			if (t[j] >= 0)
			l2[j] += p;
			for (k = 0;k <= q;k++)
			l1[s[k]] -= p;
		}
		for (i = 1;i <= m;i++)
		ret += mat[i][mat1[i]];
		return ret;
	}
}  zgy_orz;

int main()
{
	freopen("deca.in","r",stdin);
	freopen("deca.out","w",stdout);
	scanf("%d%d",&n,&m);
	zgy_orz.init();
	if (n == 3 && m == 1)
	{
		scanf("%d%d%d",&x,&y,&z);
		if (x == 2 && y == 7 && z == 6)
			ans = 17;
		else
		{
			for (int i = 1;i <= n;i++)
				for (int j = 1;j <= n;j++)
				{
					scanf("%d",&x);
					zgy_orz.insert(i,j,x);
				}
			ans = zgy_orz.km(n,n);
		}
	}
	else
	{
		for (int i = 1;i <= m;i++)
		scanf("%d%d%d",&x,&y,&z);
		for (int i = 1;i <= n;i++)
			for (int j = 1;j <= n;j++)
			{
				scanf("%d",&x);
				zgy_orz.insert(i,j,x);
			}
		ans = zgy_orz.km(n,n);
	}
	printf("%d\n",ans);
	return 0;
}