/*
ZADATAK: drzave
JEZIK: C++
*/
#include <iostream.h>
#include <fstream.h>

const int MAXN=100;
const int MAXM=8;
const int MAXK=64;

int n,m,k;
int autoput[MAXN][MAXM][MAXM];
int put[MAXN][MAXM][MAXM];
int tura_do[MAXN][MAXM], tura_d[MAXN][MAXM];
int ob[MAXM];
int ttura[MAXM], tntura;

long min;

void tura(int z, int i){
	ob[i]=1;
	int j;
	for (j=0;j<m;j++) if (ob[j]==0 && put[z][i][j]>0) tura(z,j);
	ttura[tntura++]=i;
}

void minim(long &m, long d){
	if (d<m) m=d;
}

void dfs(int z, int i, long d){
//	cout<<z<<" "<<i<<" "<<d<<endl;
	if (tura_do[z][i]==-1) return;
	if (z==n-1) {minim( min, d+tura_d[z][i] ); return;}

	int j;
	for (j=0;j<m;j++)
		if (autoput[z][ tura_do[z][i] ][j])
			dfs(z+1,j, d+tura_d[z][i]+autoput[z][ tura_do[z][i] ][j]);
}

int main(){

	int i,j,z;
    
//	ifstream fin("zad3.txt");
	//fin>>n>>m>>k;
	cin>>n>>m>>k;
	int x,y,d;

	for (z=0;z<n;z++)
		for (i=0;i<m;i++)
			for (j=0;j<m;j++) autoput[z][i][j]=0;

	for (z=0;z<n;z++){
		for (i=0;i<m;i++)
			for (j=0;j<m;j++) //fin>>put[z][i][j];
				cin>>put[z][i][j];
		if (z!=n-1){
			for (i=0;i<k;i++) {
				//fin>>x>>y>>d;
				cin>>x>>y>>d;
				if (autoput[z][x-1][y-1]==0 || (autoput[z][x-1][y-1]>d) ) autoput[z][x-1][y-1]=d;
			}
		}
	}
	//fin.close();



	for (z=0;z<n;z++){
		for (i=0;i<m;i++){
				for (x=0;x<m;x++) ob[x]=0;
				tntura=0;
				tura(z,i);
				if (tntura==m){
					tura_do[z][i]=ttura[0];
					tura_d[z][i]=0;
					for (x=m-2;x>=0;x--) 
						if (put[z][ ttura[x+1] ][ ttura[x] ]==0) break; else
							tura_d[z][i]+=put[z][ ttura[x+1] ][ ttura[x] ];
					if (x>=0){
						tura_do[z][i]=-1;
						tura_d[z][i]=0;
					}
				}
			}
	}


/*
	for (z=0;z<n;z++){
		cout<<endl<<"Zemlja "<<z<<endl;
		for (i=0;i<m;i++)
			cout<<i<<" "<<tura_do[z][i]<<" "<<tura_d[z][i]<<endl;
	}
	cout<<endl<<endl;
*/

	min=2000000;

	for (i=0;i<m;i++)
		if (tura_do[0][i]!=-1) dfs(0,i,0);

	cout<<min<<endl;

    return 0;
}
