#include #include #include #include using namespace std; template class maxflow { struct edge {int to, rep; T cap; edge(int t, int r, T c) : to(t), rep(r), cap(c) {}}; std::vector> g; std::vector dis, id; public: maxflow(int n) : g(n), id(n), dis(n) {} void add_edge(int s, int t, T f) { g[s].push_back({t, (int)g[t].size() + (s == t), f}); g[t].push_back({s, (int)g[s].size() - 1, 0}); } T flow(int s, int t) { T ret = 0; while (bfs(s, t)) { id.assign(id.size(), 0); ret += path(s, t, T((1LL << 60) | (1 << 30))); } return ret; } private: bool bfs(int s, int t) { dis.assign(g.size(), g.size()); dis[s] = 0; std::queue q; for (q.push(s); !q.empty(); q.pop()) { int now = q.front(); for (auto &v : g[now]) { if (v.cap > 0 && dis[v.to] > dis[now] + 1) { dis[v.to] = dis[now] + 1; q.push(v.to); } } } return dis[t] < g.size(); } T path(int s, int t, T lim) { if (s == t) return lim; T now = 0; for (int &i = id[t]; i < g[t].size(); ++i) { auto &e = g[t][i], &re = g[e.to][e.rep]; if (re.cap <= 0 || dis[e.to] >= dis[t] || dis[e.to] < 0) continue; T tmp = path(s, e.to, std::min(lim - now, re.cap)); if (tmp == 0) continue; e.cap += tmp; re.cap -= tmp; now += tmp; if (now >= lim) break; } return now; } }; int main() { int n; cin >> n; vector p(n); long long all = 0; for (int i = 0; i < n; ++i) cin >> p[i]; int m; cin >> m; vector u(m), v(m); for (int i = 0; i < m; ++i) cin >> u[i] >> v[i]; int k; cin >> k; maxflow mf(n + k + 2); int sorce = n + k, sink = sorce + 1; for (int i = 0; i < n; ++i) { if (p[i] > 0) { all += p[i]; mf.add_edge(sorce, i, 0); mf.add_edge(i, sink, p[i]); } else { mf.add_edge(sorce, i, -p[i]); mf.add_edge(i, sink, 0); } } long long inf = 1e14; for (int i = 0; i < m; ++i) { --u[i], --v[i]; mf.add_edge(u[i], v[i], inf); } for (int i = 0; i < k; ++i) { int a, b, s; cin >> a >> b >> s; all += s; --a, --b; mf.add_edge(a, i + n, inf); mf.add_edge(b, i + n, inf); mf.add_edge(i + n, sink, s); } long long ans = all - mf.flow(sorce, sink); cout << ans << endl; }