/*
ZADATAK: drzave
JEZIK: c
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MCON 10

typedef enum{false,true} Bool;
long a[101][MCON][MCON], b[101][MCON][MCON], act[MCON];
long N,M,K,Rez,BrPer;
short GenPer[40500][MCON];
const char *ulaz= "drzave.in";
const char *izlaz="drzave.out";



void Citaj();
void Init();
void Uradi();
void GPer(int);
void GGPer();
void Ispisi();

int main(){

	Init();
	Citaj();
	GGPer();
	Uradi();
	Ispisi();
	return 0;
}

void Ispisi(){
	FILE *fout=stdout;//fopen(izlaz,"w");
	fprintf(fout,"%ld",Rez);
//	  fclose(fout);
}
void Uradi(){
	int i,j,l;
	long min;

	for(i=N;i>0;i--){
		GPer(i);	//nakon GPer u act se nalaze minimalne duzine putanja od
					//bilo kog grada drzave i.

		for(j=1;j<=M;j++){a[i-1][M+1][j]=0; a[i-1][j][M+1]=0;}

		for(j=1;j<=M;j++)
			for(l=1;l<=M;l++)
				if(b[i-1][j][l]>0 && act[l]>0) {
					if (a[i-1][j][M+1]==0){a[i-1][j][M+1]=b[i-1][j][l]+act[l];}
					else {
						if (a[i-1][j][M+1]>b[i-1][j][l]+act[l]) 
							a[i-1][j][M+1]=b[i-1][j][l]+act[l];
					}
				}
		if (i!=1) for(j=1;j<=M+1;j++) act[j]=0;
	}
	min=0;
	for(i=1;i<=M;i++)
		if((act[i]>0) &&((min>act[i])||(min==0))) min=act[i];
	Rez=min;
}

void GPer(int broj){
	long per[MCON];
	Bool ok;
	int i,j;
	long zbir,br=0;

	for(i=0;i<BrPer;i++){
		for(j=1;j<=M+1;j++) per[j]=GenPer[i][j];
		//provera da li je putanja moguca
		zbir=0; ok=true;
		for(j=2;j<=M+1;j++)
			if ((a[broj][per[j-1]][per[j]]>0)||(a[broj][per[j-1]][per[j]]==0 && j==M+1 && broj==N) )
				zbir+=a[broj][per[j-1]][per[j]];
			else ok=false;
		if ((ok==true)&&(((act[per[1]]>zbir)&&(act[per[1]]!=0))||(act[per[1]]==0))) {
			act[per[1]]=zbir;
		}
		//kraj provere
	}
}
void GGPer(){
	short per[MCON];
	Bool bio[MCON], ok;
	int i,j,k,l;

	for(i=1;i<=M+1;i++) {per[i]=i; bio[i]=true;}
	BrPer=0;

	for(;;){
		for(i=1;i<=M+1;i++) GenPer[BrPer][i]=per[i];
		BrPer++;
		//sledeca permutacija
		k=M; ok=false;
		while((k>0)&&(ok==false)){
			for(i=per[k]+1;i<=M;i++)
				if(bio[i]==false) {
					bio[per[k]]=false;
					per[k]=i;
					bio[i]=true;
					ok=true;
					for(j=k+1;j<=M;j++)
						for(l=1;l<=M;l++)
							if(bio[l]==false){
								bio[l]=true; per[j]=l;
								break;
							}
				}
				if (ok==false){
					bio[per[k]]=false;
					per[k]=0; k--;
				}
		}
		if (k==0) break;
	}
}

void Init(){
	int i,j,l;

	for(i=1;i<=M;i++) {
		act[i]=0; a[N][i][M+1]=0; a[N][M+1][i]=0;
	}
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++)
			for(l=1;l<=M;l++){ 
				a[i][j][l]=0;
				if (i<N) b[i][j][l]=0;
			}
}

void Citaj(){
	FILE *fin=stdin;//fopen(ulaz,"r");
	int g1,g2,d,i,j,l;

	fscanf(fin,"%d%d%d",&N,&M,&K);
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++)
			for(l=1;l<=M;l++) fscanf(fin,"%d",&a[i][j][l]);
		if(i!=N){
			for(j=0;j<K;j++){
				fscanf(fin,"%d%d%d",&g1,&g2,&d);
				b[i][g1][g2]=d;
			}
		}
	}
//	  fclose(fin);
}