#include <bits/stdc++.h>//状压bfs ,讲不通的状态压缩成2进制代码 
using namespace std;
int ck[15][15][15][15];//存两个各自之间是否存在墙/门或者是啥都没有
int vis[15][15][9024];//判断是否是两个完全相同的状态,只有所处位置一样，而且所拿药匙相同才会相同 
int dir[4][2]={1,0,-1,0,0,1,0,-1};
struct node{
	int x,y,stp,key;//key表示目前拿到的钥匙 
};
queue<node> q;
int key[15][15];
int n,m,p,k;
int bfs()
{
	q.push((node){1,1,0,key[1][1]});
	vis[1][1][key[1][1]]=1;
	while(!q.empty())
	{
		node now=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int x=now.x+dir[i][0],y=now.y+dir[i][1],ky=now.key,stp=now.stp+1;
			if(x<=0||y<=0||x>n||y>m) continue;
			if((ck[now.x][now.y][x][y]&ky)!=ck[now.x][now.y][x][y]) continue;
			ky|=key[x][y];
			if(vis[x][y][ky]) continue;
			vis[x][y][ky]=1;
			if(x==n&&y==m) return stp;
			q.push((node){x,y,stp,ky});
 		}
	}
	return -1;
 } 
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	scanf("%d",&k);
	int x1,y1,x2,y2,g,s;
	for(int i=1;i<=k;i++)
	{
		scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
		if(g==0) ck[x1][y1][x2][y2]=ck[x2][y2][x1][y1]=1<<(p);
		else ck[x1][y1][x2][y2]=ck[x2][y2][x1][y1]=1<<(g-1);
	}
	scanf("%d",&s);
	for(int i=1;i<=s;i++)
	{
		scanf("%d%d%d",&x1,&y1,&g);
		key[x1][y1]|=1<<(g-1);
	}
	int ans=bfs();
	printf("%d",ans);
}