// 01BFS最短路+状压 O(NM*2^P)
#include<bits/stdc++.h>
using namespace std;

const int N=11;
int n,m,p,k,s;
int e[N][N][4],key[N][N];
bool vis[N][N][1<<10];
struct node{ //格点状态
  int x,y,s,d; //坐标，钥匙状态，到起点的距离
};
int dx[]{1,0,-1,0},dy[]{0,1,0,-1}; //下，右，上，左

int bfs(){
  deque<node> q;
  q.push_back({1,1,0,0});
  while(!q.empty()){
    auto [x,y,s,d]=q.front(); q.pop_front();
    if(x==n && y==m) return d;
    if(vis[x][y][s])continue; vis[x][y][s]=1;
    
    if((s|key[x][y])!=s) q.push_front({x,y,s|key[x][y],d}); //有新钥匙的状态放队首
    for(int i=0; i<4; ++i){ //向四周移动
      int a=x+dx[i], b=y+dy[i];
      if(a<1||a>n||b<1||b>m) continue;
      if(e[x][y][i]==-1 || e[x][y][i]&&(s&(1<<(e[x][y][i]-1)))) //是通道||有门&&有匹配钥匙
        q.push_back({a,b,s,d+1}); //扩展的状态放队尾
    }
  }
  return -1;
}
int main(){
  cin>>n>>m>>p>>k; //p:门的种类，k:门和墙的总数
  memset(e,-1,sizeof e); //双向通路默认-1
  for(int i=0,x1,y1,x2,y2,g; i<k; ++i){ //存储相邻格点的门或墙
    cin>>x1>>y1>>x2>>y2>>g;
    for(int j=0; j<4; ++j)if(x1+dx[j]==x2&&y1+dy[j]==y2){ //j:0下1右2上3左
      e[x1][y1][j]=e[x2][y2][(j+2)%4]=g; //g=0墙，g>0门
    }
  }
  cin>>s; //s:钥匙总数
  for(int i=0,x,y,q; i<s; ++i){
    cin>>x>>y>>q;
    key[x][y]|=1<<(q-1); //二进制q-1位上保存该种钥匙
  }
  cout<<bfs();
}

#include <iostream>
using namespace std;
constexpr int N = 13, M = 13, K = 105, P = 10;
int n, m, p, k;
struct Q{
	int x, y, s, k;
	Q() {} 
	Q(int _x,int _y,int _s,int _k):
		x(_x),y(_y),s(_s),k(_k) {}
} q[N*M*(1<<P)];
int qhead, qtail;
int dr[N][M][N][M], ky[N][M];
int vst[N][M][1<<P];
int dir[4][2] = {{1,0}, {0,-1}, {0,1}, {-1,0}};
bool keyok(int keys, int door) {
	if(door > P) return false;
	return keys & (1<<door);
}
int main() {
	int tx, ty, ts, td, tk;
	int x1, y1, x2, y2, g, s;
	cin >> n >> m >> p >> k;
	for(int i = 1; i <= k; ++ i) {
		cin >> x1 >> y1 >> x2 >> y2 >> g;
		if(!g) g = -1;
		dr[x1][y1][x2][y2] = dr[x2][y2][x1][y1] = g;
	}
	cin >> s;
	for(int i = 1; i <= s; ++ i) {
		cin >> x1 >> y1 >> g;
		ky[x1][y1] |= 1 << g;
	}
	qhead = qtail = 0;
	tk = ky[1][1];
	q[++ qtail] = Q(1, 1, 0, tk);
	vst[1][1][tk] = 1;
	while(qhead <= qtail) {
		Q qt = q[++ qhead];
		for(int i = 0; i < 4; ++ i) {
			tx = qt.x + dir[i][0];
			ty = qt.y + dir[i][1];
			tk = qt.k | ky[tx][ty];
			if(tx<1 || tx>n || ty<1 || ty>m || vst[tx][ty][tk])
				continue;
			td = dr[qt.x][qt.y][tx][ty];
			if(td) {
				if(td == -1) continue;
				if(!keyok(qt.k,td)) continue;
			}
			ts = qt.s + 1;
			if(tx == n && ty == m) {
				printf("%d\n",ts);
				return 0;
			}
			q[++ qtail] = Q(tx, ty, ts, tk);
			vst[tx][ty][tk] = 1;
		}
	}
	puts("-1");
	return 0;
}