G、Pikachu

In Viridian forest there is a tree T formed by N nodes, each edge on which has a positive weight.

There is an undirected graph G generated from tree T, which contains N nodes and undirected edges, where the capacity of the edge between u and v equals to the distance between them on the tree T.

Given the tree T, Pikachu wants to calculate the sum of the max flow between every two nodes in G, there are different pairs of nodes should be counted. Could you help him?

输入描述:

The input starts with one line containing exactly one integer t, which is the number of test cases.

For each test case, the first line contains one integer N, indicating the size of the tree T.

Then followed by N - 1 lines, each consists of three integers ui, vi and wi, representing the two nodes connected by the i-th edge and the weight of the i-th edge.

- 1 ≤ t ≤ 10.
- 2 ≤ N ≤ 105.
- 1 ≤ wi ≤ 1000.
- 

输出描述:

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the sum of the maximum flow between every two nodes in G.

2
3
1 2 1
2 3 1
5
1 2 1
2 3 1
2 4 1
4 5 2

Case #1: 7
Case #2: 72