from heapq import heappush, heappop

INF = 1<<60

def encode(n, f):
    return n*6+f
def decode(n):
    return n//6, n%6

N, R, C = map(int, input().split())
X = list(map(int, input().split()))
Y = list(map(int, input().split()))
Z = list(map(int, input().split()))
S = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
for _ in range(R):
    u, v, w, a, m = map(int, input().split())
    u, v = u-1, v-1
    G[u].append((v, w, a, m, INF))
    G[v].append((u, w, a, m, INF))

for i in range(N):
    G[i].append((N, INF, INF, INF, S[i]))
    G[N].append((i, INF, INF, INF, S[i]+C))

dist = [[INF]*6 for _ in range(N+1)]
dist[0][0] = 0
visited = [[False]*6 for _ in range(N+1)]
que = [(0, encode(0, 0))]
while que:
    _, now = heappop(que)
    n, f = decode(now)
    if visited[n][f]:
        continue
    visited[n][f] = True
    for v, w, a, m, s in G[n]:
        d = w
        if 1 <= f%3:
            d = min(d, a)
        if 2 <= f%3:
            d = min(d, m)
        if f//3 == 1:
            d = min(d, s)
        if d == INF: continue
        if dist[n][f]+d < dist[v][f]:
            dist[v][f] = dist[n][f]+d
            heappush(que, (dist[v][f], encode(v, f)))
    if n < N:
        if f%3 == 0 and dist[n][f]+X[n] < dist[n][f+1]:
            dist[n][f+1] = dist[n][f]+X[n]
            heappush(que, (dist[n][f+1], encode(n, f+1)))
        if f%3 <= 1 and dist[n][f]+Y[n] < dist[n][f//3*3+2]:
            dist[n][f//3*3+2] = dist[n][f]+Y[n]
            heappush(que, (dist[n][f//3*3+2], encode(n, f//3*3+2)))
        if f//3 == 0 and dist[n][f]+Z[n] < dist[n][f+3]:
            dist[n][f+3] = dist[n][f]+Z[n]
            heappush(que, (dist[n][f+3], encode(n, f+3)))

print(min(dist[N-1]))