#include using namespace std; #include #include using namespace atcoder; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() templatebool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} templatebool chmax(T&a, const T&b){if(a> n; vector p(n); rep(i,n) cin >> p[i]; scc_graph scc(n); cin >> m; vector u(m), v(m); rep(i,m){ cin >> u[i] >> v[i]; --u[i], --v[i]; scc.add_edge(u[i], v[i]); } auto sc = scc.scc(); vector c(n,-1); int z = sc.size(); rep(i,z){ for(int x:sc[i]) c[x] = i; } mf_graph g(z+2); rep(i,m){ if(c[u[i]]==c[v[i]]) continue; g.add_edge(c[v[i]], c[u[i]], INFLL); } cin >> k; rep(i,k){ int a,b,s; cin >> a >> b >> s; --a, --b; p[a] += s; if(c[a]!=c[b]) g.add_edge(c[a], c[b], s); } vector tot(z,0); rep(i,n) tot[c[i]] += p[i]; ll ans = 0; rep(i,z){ ans += max(0LL, tot[i]); g.add_edge(z, i, max(0LL, tot[i])); g.add_edge(i, z+1, -min(0LL, tot[i])); } cout << ans-g.flow(z,z+1) << '\n'; return 0; }