// https://szkopul.edu.pl/problemset/problem/l8-ujU0a7HQFxy8UY32B4Kk_/site/?key=statement

#include <algorithm>
#include <bitset>
#include <iostream>
#include <queue>
#include <vector>

constexpr int MAX_N = 5 * 1001, MAX_M = 100 * 1001;

int values[MAX_N];
int values1[MAX_N];
int cost[MAX_N];
std::bitset<MAX_N> visited;

std::vector<std::pair<int, int>> kra1[MAX_N];
std::vector<std::pair<int, int>> kra2[MAX_N];

void Dijkstra(int v, int* arr, std::vector<std::pair<int, int>>* kra) {
    std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> q;

    q.push({0, v});
    arr[v] = 0;

    while (!q.empty()) {
        const auto [o, w] = q.top();
        q.pop();

        if (visited[w]) {
            continue;
        }

        visited[w] = true;
        arr[w] = o;

        for (const auto& [u, d] : kra[w]) {
            if (!visited[u]) {
                q.push({d + o, u});
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n;
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        std::cin >> cost[i];
    }

    int m;
    std::cin >> m;

    for (int i = 0; i < m; i++) {
        int a, b, c;
        std::cin >> a >> b >> c;

        kra1[a].push_back({b, c});
        kra2[b].push_back({a, c});
    }

    Dijkstra(1, values, kra1);

    std::vector<int> v;

    for (int i = 2; i <= n; i++) {
        if (visited[i]) {
            v.push_back(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        visited[i] = false;
    }

    for (int i = 1; i <= n; i++) {
        values1[i] = -1;
    }

    Dijkstra(1, values1, kra2);

    int ans = cost[1] / 2;

    for (const auto& u : v) {
        if (values1[u] == -1) {
            continue;
        }

        ans = std::min(ans, cost[u] / 2 + values[u] + values1[u]);
    }

    std::cout << ans << '\n';

    return 0;
}