Two Companies

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
The tram service will start its' work soon in Bytetown  the capital of Byteland. There are N junctions in Bytetown and N1 tram ways between them. Every tram way connects some two distinct junctions. It's possible to go from any junction to any other one using a sequence of tram ways and there is only one way to go from one junction to another one. So, we can conclude that the graph consisting of junctions as vertices and tram ways as edges is a tree.
What has not been decided yet is the set of tram routes. Two companies  BytelandTramService (BTS) and GlobalTramNetworks (GTN) have proposed their own plans of tram routes. Each plan has a number of routes and for every route it has a starting junction, a final junction and the amount of joy that one will get by using this route (that was figured out by the BTS and the GTN analysts).
The problem is that these two companies don't cooperate. So, if there's at least one junction that's present at the same time, in the route of BTS and of GTN, there is a risk of collision.
The final decision was to choose some subset of the set of BTS's routes and some subset of GTN's routes in such a way that no two routes from the BTS's subset and from the GTN's subset intersect. But BTS's chosen routes can intersect with each other and GTN's chosen routes can intersect with each other. Please, find the maximal possible sum of amounts of joy of the chosen routes.
Input
The first line of input consists of three space separated integers  N, M_{1} and M_{2}  the number of junctions, the number of routes in BTS' plan and the number of routes in GTN's plan.
The next N1 lines of input describe tram ways. Each tram way is described by two space separated integers  X_{i} and Y_{i} with the meaning that the junctions with the numbers X_{i} and Y_{i} are connected with a tram way.
Then there are M_{1} lines, describing the
route plan of BTS. Each line consists of three integers: Bx_{i}, By_{i} and Bj_{i}  the starting junction, the final junction and the amount of joy that one will get using this route respectively.
Then there are M_{2} lines, describing the route plan of GTN. Each line consists of three integers: Gx_{i}, Gy_{i} and Gj_{i}  the starting junction, the final junction and the amount of joy that one will get using this route respectively.
Output
Output the maximal possible sum of amounts of joy over all the chosen roads.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ M_{1}, M_{2} ≤ 700
 1 ≤ X_{i}, Y_{i} ≤ N
 1 ≤ Bx_{i}, By_{i}, Gx_{i}, Gy_{i} ≤ N
 1 ≤ Bj_{i}, Gj_{i} ≤ 10^{6}
Example
Input: 5 2 1 1 2 2 3 3 4 4 5 1 3 7 2 5 18 2 5 11 Output: 25
Explanation
If you take the only route of GTN, you'll not be able to take anything of BTS. So, it's better to take the both routes of BTS (a route of a company can cross with another route of this company as well) and to end up with the total sum of 25.
Author:  xcwgf666 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/TWOCOMP 
Tags  hard, june14, maxflow, xcwgf666 
Date Added:  15042014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions