{
ZADATAK: drzave
JEZIK: PASCAL
}
Program drzave;
type niz=array[1..1000] of longint;
		 mat=array[1..100,1..100] of longint;
var f:text;
		n,m,k,i,l,j,tren,a,b,d,min:longint;
		R,Mark,Putdo,Kraj:niz;
		T,E,Putizmedju:mat;

procedure nadjiput(br:longint);
	var i,suma:longint;
	begin
		if tren<m
		then
			begin

				for i:=1 to m do
					begin
						if (Mark[i]=0) and (T[br,i]>0)
						then
							begin
								tren:=tren+1;
								R[tren]:=i;
								Mark[i]:=1;
								nadjiput(i);
								Mark[i]:=0;
								tren:=tren-1
							end
					end
			end
		else
			begin
				suma:=0;
				for i:=1 to m-1 do
					suma:=suma+T[R[i],R[i+1]];
				if suma<E[R[1],R[m]]
				then
					E[R[1],R[m]]:=suma;
			end
	end;







begin
	{assign(f,'test.dat');
	reset(f);}
	read(n);
	read(m);
	read(k);
	for i:=1 to m do
		Putdo[i]:=0;
	for l:=1 to n-1 do
		begin
			for i:=1 to m do
				for j:=1 to m do
					read(T[i,j]);

			for i:=1 to m do
				for j:=1 to m do
					E[i,j]:=1000000000;


			tren:=0;
			for i:=1 to m do
				begin
					tren:=tren+1;
					R[tren]:=i;
					Mark[i]:=1;
					nadjiput(i);
					tren:=tren-1;
					Mark[i]:=0
				end;


				for j:=1 to m do
					Kraj[j]:=1000000000;

			for i:=1 to m do
				for j:=1 to m do
					if E[i,j]+Putdo[i]<Kraj[j] then
						Kraj[j]:=E[i,j]+Putdo[i];




			for i:=1 to m do
				for j:=1 to m do
					Putizmedju[i,j]:=1000000000;

			for i:=1 to k do
				begin
					read(a);
					read(b);
					read(d);
					Putizmedju[a,b]:=d;
				end;

			for i:=1 to m do
				Putdo[i]:=1000000000;

			for i:=1 to m do
				begin
					for j:=1 to m do
						if Kraj[j]+Putizmedju[j,i]<Putdo[i]
						then
							Putdo[i]:=Kraj[j]+Putizmedju[j,i]
				end;





				{	for i:=1 to m do
						begin
							min:=2000000000;
							for j:=1 to m do
								if E[j,i]<min
								then
									min:=E[j,i];
							Z[i]:=min
						end
				end
			else
				begin






			for i:=1 to m do
				for j:=1 to m do
					Dizmedju[i,j]:=2000000000;

			for i:=1 to m do
				Dali[i]:=0;
			for i:=1 to k do
				begin
					read(f,a);
					read(f,b);
					if Dali[b]=0
					then
						Dali[b]:=1;
					read(f,d);
					Dizmedju[a,b]:=d;
				end;  }
		end;



	for i:=1 to m do
				for j:=1 to m do
					read(T[i,j
			else
				begin






			for i:=1 to m do
				for j:=1 to m do
					Dizmedju[i,j]:=2000000000;

			for i:=1 to m do
				Dali[i]:=0;
			for i:=1 to k do
				begin
					read(f,a);
					read(f,b);
					if Dali[b]=0
					then
					
				for j:=1 to m do
					Kraj[j]:=1000000000;

			for i:=1 to m do
				for j:=1 to m do
					if E[i,j]+Putdo[i]<Kraj[j] then
						Kraj[j]:=E[i,j]+Putdo[i];


	 {close(f);}
	 min:=1000000000;
	 for i:=1 to m do
		 if Kraj[i]<min
		 then
			 min:=Kraj[i];


	 writeln(min);






	{for i:=1 to m do
		begin
			for j:=1 to m do
				write(E[i,j]:3);
			writeln
		end;}
end.