#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <deque>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 11, M = 360, P = 1 << 10;  // 状态压缩

int n, m, k, p;
int head[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];  // key[i]存的是编号为i的格子存在的钥匙的状态(可以有多把)
int dist[N * N][P];  // dist[i][state] 意思是在第i个格子并且状态为state的最短路径
bool st[N * N][P];  // st[i][state]意思是格子i且状态为state是否在队列中

set<PII> edges;

void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = head[a];
    w[idx] = c;
    head[a] = idx ++;
}

void build() {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            for (int u = 0; u < 4; u ++) {
                int x = i + dx[u], y = j + dy[u];  //  查看附近可转移的状态
                if (!x || x > n || !y || y > m) continue;  // 检查是否合法
                int a = g[i][j], b = g[x][y];
                // 如果a和b之间没有阻隔, 直接建一条边权为0的边(边权为0代表无锁)
                if(!edges.count({a, b})) add(a, b, 0);  
            }
}

// 双端队列宽搜
int bfs() {
    memset(dist, 0x3f, sizeof dist);
    dist[1][0] = 0;  // 从格子1开始,手上一条钥匙都没有state = 0

    deque<PII> q;
    q.push_back({1, 0});

    while (q.size()) {
        PII t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;

        if (t.x == n * m) return dist[t.x][t.y];  // 到了大兵所在的位置

        // 这个格子有钥匙, 那么来一发状态转移,捡起钥匙
        if (key[t.x]) {
            // 捡起来,进入状态state
            int state = t.y | key[t.x];
            // 更新一下在这个格子t.x下,到达状态state的路径的最短距离
            if (dist[t.x][state] > dist[t.x][t.y]) {
                dist[t.x][state] = dist[t.x][t.y];  // 捡钥匙是不费时间的
                q.push_front({t.x, state});
            }
        }

        // 无钥匙, 要往四周走, 来一发状态转移
        for (int i = head[t.x]; i != -1; i = ne[i]) {
            int j = e[i];  // 去下一个临近的点
            if (w[i] && !(t.y >> w[i] - 1 & 1)) continue;  // 有锁并且当前状态无钥匙
            // 有钥匙,并且可以更新状态
            if (dist[j][t.y] > dist[t.x][t.y] + 1) {
                dist[j][t.y] = dist[t.x][t.y] + 1;
                q.push_back({j, t.y});
            }
        }
    }

    return -1;
}

int main() {
    cin >> n >> m >> p >> k;

    // 给格子编号,按行顺序走 1~n, n+1~2n+1...
    for (int i = 1, t = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            g[i][j] = t ++;

    memset(head, -1, sizeof head);
    // 处理门
    while (k --) {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        int a = g[x1][y1], b = g[x2][y2];  // 获得两个格子的编号

        // 只要有两个相邻且有阻碍的格子,直接加边
        // 所以edges存的是存在阻隔的两个格子
        edges.insert({a, b}), edges.insert({b, a});  
        if (c) add(a, b, c), add(b, a, c);  // 如果是门的话可以建边, 不过边权为c
    }

    build();  // 建造地图

    int s;
    cin >> s;
    // 处理钥匙
    while (s --) {
        int x, y, c;
        cin >> x >> y >> c;
        key[g[x][y]] |= 1 << c - 1;   // 状态压缩,存储该地图有的钥匙
    }

    cout << bfs() << endl;

    return 0;
}