#include <bits/stdc++.h>
using namespace std;

struct State {
    int x, y, keys, steps;
};

int n, m, p;
int door[11][11][11][11]; 
int key[11][11]; 
int vis[11][11][1<<10];

int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};

int bfs() {
    queue<State> q;
    q.push({1,1,key[1][1],0});
    vis[1][1][key[1][1]] = 1;

    while(!q.empty()) {
        State cur = q.front(); q.pop();
        if(cur.x==n && cur.y==m) return cur.steps;

        for(int i=0; i<4; i++) {
            int nx=cur.x+dx[i], ny=cur.y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;

            int type = door[cur.x][cur.y][nx][ny];
            if(type == 0) {
                continue; 
            }
            if(type>0 && !(cur.keys&(1<<(type-1)))){ 
                continue;
            }
            int new_keys = cur.keys | key[nx][ny];
            if(!vis[nx][ny][new_keys]) {
                vis[nx][ny][new_keys] = 1;
                q.push({nx,ny,new_keys,cur.steps+1});
            }
        }
    }
    return -1;
}

int main() {
    memset(door, -1, sizeof(door));
    int k; 
    cin>>n>>m>>p>>k;
    while(k--) {
        int x1,y1,x2,y2,g;
        cin>>x1>>y1>>x2>>y2>>g;
        door[x1][y1][x2][y2] = door[x2][y2][x1][y1] = g;
    }
    int s; cin>>s;
    while(s--) {
        int x,y,q; 
        cin>>x>>y>>q;
        key[x][y] |= (1<<(q-1));
    }
    cout << bfs() << endl;;
    return 0;
}