#include <bits/stdc++.h>
#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define printv(a, b) { \
for(auto pv : a) b << pv << " "; \
b << "\n"; \
}
using namespace std;
typedef long long ll;
using pii = pair<int, int>;
struct seg{
int l, r, id;
bool operator<(seg b) const {
return l < b.l;
}
};
ostream& operator<<(ostream& o, seg s){
return o << '(' << s.l << ',' << s.r << ',' << s.id << ')';
}
vector<vector<int>> g, star;
vector<int> lp, rp;
vector<int> a, X, Y;
vector<ll> C;
vector<vector<ll>> dp;
vector<ll> sub;
int n;
void dfs(int now){
ll total = 0;
for(int i : star[now]) total += C[i];
sub[now] = total;
ll sum = 0;
for(int i : g[now]){
dfs(i);
}
vector<ll> tmp(n + 1);
for(int i = 0; i <= n; i++){
for(int j : g[now]) tmp[i] += dp[j][i];
}
ll cn = total + tmp[0];
for(int i : star[now]){
int x = X[i];
cn = min(cn, tmp[x] + total - C[i]);
}
for(int i = 0; i <= n; i++){
if(lp[now] <= i && i <= rp[now]) dp[now][i] = total + tmp[i];
else dp[now][i] = cn;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
vector<pii> e;
a.resize(n + 1);
for(int i = 1; i <= n; i++){
cin >> a[i];
e.eb(mp(a[i], i));
}
int m;
cin >> m;
X.resize(m + 1);
Y.resize(m + 1);
C.resize(m + 1);
for(int i = 1; i <= m; i++){
cin >> X[i] >> Y[i] >> C[i];
e.eb(mp(Y[i], -i));
}
gsort(e);
set<seg> st;
st.insert(seg({1, n, 1}));
int ts = 1;
g.resize(2);
star.resize(2);
lp.resize(2);
rp.resize(2);
lp[1] = 1;
rp[1] = n;
for(int i = 0; i < e.size(); ){
int y = e[i].F;
for(; i < e.size() && e[i].F == y; i++){
if(e[i].S > 0){
int pos = e[i].S;
auto it = st.upper_bound(seg({pos, 0, 0}));
if(it == st.begin()) continue;
it--;
if(it->r < pos) continue;
int l = it->l, r = it->r;
int id = it->id;
st.erase(it);
if(l < pos){
st.insert(seg({l, pos - 1, ++ts}));
g.eb(); star.eb(); lp.eb(); rp.eb();
g[id].eb(ts);
lp[ts] = l;
rp[ts] = pos - 1;
}
if(pos < r){
st.insert(seg({pos + 1, r, ++ts}));
g.eb(); star.eb(); lp.eb(); rp.eb();
g[id].eb(ts);
lp[ts] = pos + 1;
rp[ts] = r;
}
//cerr << "split\n";
//printv(st, cerr);
continue;
}
int id = -e[i].S;
//cerr << "add star " << id << "\n";
//printv(st, cerr);
int x = X[id];
auto it = st.upper_bound(seg({x, 0, 0}));
it--;
int v = it->id;
star[v].eb(id);
}
}
/*for(int i = 1; i <= ts; i++){
cerr << "seg " << i << " " << lp[i] << " ";
printv(star[i], cerr);
printv(g[i], cerr);
}*/
dp.resize(ts + 1, vector<ll>(n + 1));
sub.resize(ts + 1);
dfs(1);
cout << dp[1][0] << "\n";
return 0;
}
