#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<set>
#include<map>

int main()
{
	int N;
	std::cin >> N;
	std::vector<std::int64_t> cost(N);
	for (auto& c : cost)
	{
		std::cin >> c;
	}
	std::vector<std::map<int, std::int64_t>> edge(N);
	int M;
	std::cin >> M;
	for (int i = 0; i < M; ++i)
	{
		int A, B;
		std::int64_t C;
		std::cin >> A >> B >> C;
		edge[A][B] = C;
		edge[B][A] = C;
	}
	std::int64_t ecost[50][50];
	for (int i = 0; i < N; ++i)
	{
		for (int k = 0; k < N; ++k)
		{
			ecost[i][k] = std::numeric_limits<int>::max();
			if (edge[i].count(k))
			{
				ecost[i][k] = edge[i][k];
			}
		}
	}
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			for (int k = 0; k < N; ++k)
			{
				ecost[j][k] = std::min(ecost[j][k], ecost[j][i] + ecost[i][k]);
			}
		}
	}
	std::int64_t min = std::numeric_limits<int>::max();
	for (int i = 1; i < N - 1; ++i)
	{
		for (int k = 1; k < N - 1; ++k)
		{
			if (i == k)
			{
				continue;
			}
			min = std::min(min,
				cost[i] + cost[k] + ecost[0][i] + ecost[i][k] + ecost[k][N - 1]);
		}
	}

	std::cout << min << std::endl;
}