#include<cstdio>
#include<cstring>
#include<queue>

using namespace std;
  
struct edge{
  int x,y,l,c;
  int next;
};

  edge v[10000];
  int head[50];
  int k[50],p[50],a[50];
  int s[50][50];
  int d[50];
  int last[50];
  int f[50];
  int n,m;
  int x;
  int tot=1;
  int st,ed;
  int sum=0;
  int ans=0;

void add(int x,int y,int l,int c){
  tot++;
  v[tot].x=x;
  v[tot].y=y;
  v[tot].l=l;
  v[tot].c=c;
  v[tot].next=head[x];
  head[x]=tot;
}

bool bfs(){
  for (int i=st;i<=ed;i++){
    d[i]=-0x3f3f3f3f;
  }
  queue<int> q;
  q.push(st);
  d[st]=0;
  int now=0;
  while (!q.empty()){
    now=q.front();
    q.pop();
    f[now]=0;
    for (int x=head[now];x;x=v[x].next){   
      if (v[x].l>0&&d[v[x].y]<d[now]+v[x].c){
        d[v[x].y]=d[now]+v[x].c;
        last[v[x].y]=x;
        if (!f[v[x].y]){
          f[v[x].y]=1;
          q.push(v[x].y);
        }
      }
    }
  }
  if (d[ed]!=-0x3f3f3f3f){
    return 1;
  }
  return 0;
}

void updata(){
  int flow=0x3f3f3f3f;
  for (int x=last[ed];x;x=last[v[x^1].y]){
    flow=min(flow,v[x].l);
  }
  for (int x=last[ed];x;x=last[v[x^1].y]){
    v[x].l-=flow;
    v[x^1].l+=flow;
  }
  ans+=flow*d[ed];
}

int main(){
  freopen("deca.in","r",stdin);
  freopen("deca.out","w",stdout);
  
  scanf("%d%d",&n,&m);
  st=0;
  ed=n+n+1;
  sum=n+n+1;
  for (int i=1;i<=m;i++){
    scanf("%d%d%d",&k[i],&p[i],&a[i]);
  }
  for (int i=1;i<=n;i++){
    for (int j=1;j<=n;j++){
      scanf("%d",&x);
      add(i,j+n,1,x);
      add(j+n,i,0,-x);
    }
  }
  
  for (int i=1;i<=n;i++){
    add(st,i,1,0);
    add(i,st,0,0);
    add(i+n,ed,1,0);
    add(ed,i+n,0,0);
  }
  
  while (bfs()){
    updata();
  }
  printf("%d\n",ans);
  return 0;
}