#include using namespace std; using ll =long long; #include using namespace atcoder; const ll INF=1e15; void solve(){ ll N; cin>>N; mf_graph G(N+202); ll S=0; for(int i=0;i>X; if(X>=0){ S+=X; G.add_edge(i,N+1,X); } else{ G.add_edge(N,i,-X); } } ll M; cin>>M; for(int i=0;i>u>>v; u--;v--; G.add_edge(v,u,INF); } cin>>M; ll c=N+2; for(int i=0;i>u>>v>>w; u--;v--; S+=w; G.add_edge(c,N+1,w); G.add_edge(u,c,INF); G.add_edge(v,c,INF); c++; } cout<>T; while(T--)solve(); }