N = int(1e20)
w = [[N for i in range(102)] for i in range(102)]
d = [[0 for i in range(102)] for i in range(102)]
b = [[0 for i in range(1002)] for i in range(102)]
s = [[0 for i in range(1002)] for i in range(102)]
def Floyd(n, k):
for k in range(1, n + 1):
for u in range(1, n + 1):
for v in range(1, n + 1):
w[u][v] = min(w[u][v], w[u][k] + w[k][v])
for u in range(1, n + 1):
for v in range(1, n + 1):
for i in range(1, k + 1):
if s[v][i] != -1 and b[u][i] != -1:
d[u][v] = max(d[u][v], s[v][i] - b[u][i])
def Check(n, v):
dp = [[N * N for i in range(102)] for i in range(102)]
for i in range(1, n + 1):
for j in range(1, n + 1):
dp[i][j] = w[i][j] * v - d[i][j]
for k in range(1, n + 1):
for u in range(1, n + 1):
for v in range(1, n + 1):
dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v])
for u in range(1, n + 1):
for v in range(1, n + 1):
if u != v and dp[u][v] + dp[v][u] <= 0:
return True
return False
n, m, k = map(int, input().split())
for i in range(1, n + 1):
w[i][i] = 0
a = list(map(int, input().split()))
t = 0
for j in range(1, k + 1):
b[i][j] = a[t]
s[i][j] = a[t + 1]
t = t + 2
for i in range(0, m):
u, v, c = map(int, input().split())
w[u][v] = c
Floyd(n, k)
l = -N
r = N
while l <= r:
mid = (l + r) // 2
if Check(n, mid):
l = mid + 1
else:
r = mid - 1
print(r)
