Long long ago, Wuhan University locates a plain with the same height. There are N points in
WHU which are connected by N − 1 edges (just like a tree) and their initial height is 0 meters.
Now we want to heap up sail on the points to form peaks and you should answer the number and
the height of the highest peak.
First line is N and K, the number of the points and the number of actions to head up.
(0 < N,K ≤ 5 × 10 5 )
Next N − 1 lines includes two numbers X and Y , meaning that the point X and point Y are
connected directly. (0 < X,Y ≤ N)
In the following K lines, each line consists of three integers X,Y,H, means that we
will heap up H meters high soil in every points belonging to the path from X to
Y (X ̸= Y,0 < X,Y ≤ N,0 ≤ H ≤ 10 9 ).
The number and the height of the highest peak (if there are servel highest peaks, select the one
who has the smallest number).
5 4
1 2
1 3
2 4
3 5
1 2 5
3 5 6
4 5 9
1 5 1
3 16