'''
多维状态BFS
'''

from collections import deque

m, n, p = map(int, input().split())
mm = int(input())
link = {}
key = {}
visit = set()

for _ in range(mm):
    i1, j1, i2, j2, t = map(int, input().split())
    link[(i1, j1, i2, j2)] = t
    link[(i2, j2, i1, j1)] = t

mm = int(input())
for _ in range(mm):
    i, j, t = map(int, input().split())
    if (i, j) not in key:
        key[(i, j)] = []
    key[(i, j)].append(t)


que = deque()
state = [0, 1, 1]       # 状态定义[经过的步长，i坐标，j坐标，钥匙1, 钥匙2 .......]
if (1, 1) in key:
    keys = []
    for k in key[(1, 1)]:
        keys.append(k)
    keys.sort()
    state.extend(keys)

que.append(tuple(state))
best_stat = {tuple(state[1:]): 0}

ans = -1
while len(que) > 0:
    cur_stat = que.popleft()
    #print(cur_stat)

    if cur_stat[1] == m and cur_stat[2] == n:
        ans = cur_stat[0]
        break

    for ii, jj in [(cur_stat[1]-1, cur_stat[2]), (cur_stat[1]+1, cur_stat[2]), (cur_stat[1], cur_stat[2]-1), (cur_stat[1], cur_stat[2]+1)]:

        if not (ii >= 1 and ii <= m and jj >= 1 and jj <= n):
            continue

        if (cur_stat[1], cur_stat[2], ii, jj) in link and link[(cur_stat[1], cur_stat[2], ii, jj)] == 0:
            continue

        cur_keys = set(cur_stat[3:])
        if (cur_stat[1], cur_stat[2], ii, jj) in link and link[(cur_stat[1], cur_stat[2], ii, jj)] > 0:
            need_key = link[(cur_stat[1], cur_stat[2], ii, jj)]
            if need_key not in cur_keys:
                continue

        new_stat = [cur_stat[0] + 1, ii, jj]
        keys = set()
        for k in cur_keys:
            keys.add(k)

        if (ii, jj) in key:
            for k in key[(ii, jj)]:
                keys.add(k)

        keys = list(keys)
        keys.sort()
        new_stat.extend(keys)

        if tuple(new_stat[1:]) in best_stat and new_stat[0] >= best_stat[tuple(new_stat[1:])]:
            continue

        best_stat[tuple(new_stat[1:])] = new_stat[0]
        que.append(tuple(new_stat))

print(ans)