Coco has a tree, whose nodes are conveniently labeled by 1,2,…,n, which has n-1 edge，each edge has a weight. An existing set S is initially empty.
Now there are two kinds of operation:
1 x： If the node x is not in the set S, add node x to the set S
2 x： If the node x is in the set S,delete node x from the set S
Now there is a annoying problem: In order to select a set of edges from tree after each operation which makes any two nodes in set S connected. What is the minimum of the sum of the selected edges’ weight ?
one integer number T is described in the first line represents the group number of testcases.( T<=10 )
For each test:
The first line has 2 integer number n,q(0<n,q<=100000) describe the number of nodes and the number of operations.
The following n-1 lines each line has 3 integer number u,v,w describe that between node u and node v has an edge weight w.(1<=u,v<=n,1<=w<=100)
The following q lines each line has 2 integer number x,y describe one operation.（x=1 or 2,1<=y<=n）
Each testcase outputs a line of "Case #x:" , x starts from 1.
The next q line represents the answer to each operation.
1 6 5 1 2 2 1 5 2 5 6 2 2 4 2 2 3 2 1 5 1 3 1 4 1 2 2 5
Case #1: 0 6 8 8 4