#!/usr/bin/env python3
# %%
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from scipy.sparse.csgraph import floyd_warshall
import numpy as np

# %%
N = int(readline())
S = np.array([readline() for _ in range(N)], np.int64)
M = int(readline())
ABC = np.array(read().split(), np.int64)
A = ABC[::3]
B = ABC[1::3]
C = ABC[2::3]

# %%
graph = np.full((N, N), np.inf)
graph[A, B] = C


# %%
dist_mat = floyd_warshall(graph, directed=False)

# %%
cost = dist_mat[0, :][:, None] + S[:, None] + dist_mat + S[None, :] + dist_mat[N - 1, :][None, :]
np.fill_diagonal(cost, np.inf)
cost = cost[1:-1, 1:-1]
answer = int(cost.min())
print(answer)