In the mathematical discipline of graph theory, the line graph of a simple undirected weighted graph $$$G$$$ is another simple undirected weighted graph $$$L(G)$$$ that represents the adjacency between every two edges in $$$G$$$.
Precisely speaking, for an undirected weighted graph $$$G$$$ without loops or multiple edges, its line graph $$$L(G)$$$ is a graph such that:
- Each vertex of $$$L(G)$$$ represents an edge of $$$G$$$.
- Two vertices of $$$L(G)$$$ are adjacent if and only if their corresponding edges share a common endpoint in $$$G$$$, and the weight of such edge between this two vertices is the sum of their corresponding edges' weight.
A minimum spanning tree(MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.
Given a tree $$$G$$$, please write a program to find the minimum spanning tree of $$$L(G)$$$.
The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.
In each test case, there is one integer $$$n(2\leq n\leq 100000)$$$ in the first line, denoting the number of vertices of $$$G$$$.
For the next $$$n-1$$$ lines, each line contains three integers $$$u,v,w(1\leq u,v\leq n,u\neq v,1\leq w\leq 10^9)$$$, denoting a bidirectional edge between vertex $$$u$$$ and $$$v$$$ with weight $$$w$$$.
It is guaranteed that $$$\sum n\leq 10^6$$$.
For each test case, print a single line containing an integer, denoting the sum of all the edges' weight of $$$MST(L(G))$$$.
2 4 1 2 1 2 3 2 3 4 3 4 1 2 1 1 3 1 1 4 1
8 4
