• .
• 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)

.

Input

The first line of the input contains an integer T(1≤T≤1000)

, denoting the number of test cases.

In each test case, there is one integer n(2≤n≤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≤u,v≤n,u≠v,1≤w≤109), denoting a bidirectional edge between vertex u and v with weight w

.

It is guaranteed that ∑n≤106

.

Output

For each test case, print a single line containing an integer, denoting the sum of all the edges' weight of MST(L(G))

.

Example

2

4

1 2 1

2 3 2

3 4 3

4

1 2 1

1 3 1

1 4 1

8

4


题解：题目给出一张图，让我们将每个边看成一个”点“，两“点”之间的权值为两边权之和。让我们找到这个“点”组成的图（题目命名为”线图“）的最小生成树的权值和。
我们可以从每条边权（即每个点的出边）的贡献入手，首先一个点的出边必须连通，否则构不成最小生成树。
那么对于特定的一个点，首先将其所有出边全部的权值加一遍，然后将其最小的一个边权乘以（这一点的度degree-2）即保证了最优解。（其实这样就是连degree-1条边使得保证最优解）
对于每一个点都这样，跑一遍即可。

#include<iostream>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<algorithm>

#include<stdio.h>

#include<map>

#include<set>

using namespace std;

typedef long long ll;

const int maxn=;

struct node

{

    int v,w;

    bool operator < (const node &r)const{

        return w<r.w;

    }

};

vector<node>G[maxn];

int main()

{

    ios::sync_with_stdio();

    int T;

    cin>>T;

    while(T--){

        int n;

        cin>>n;

        for(int i=;i<=n;i++)G[i].clear();

        for(int i=;i<=n-;i++){

            int u,v,w;

            cin>>u>>v>>w;

            G[u].push_back((node){v,w});

            G[v].push_back((node){u,w});

        }

        ll ans=;

        for(int i=;i<=n;i++){

            sort(G[i].begin(),G[i].end());

            int minn=0x3f3f3f3f;

            int degree=G[i].size();

            for(int j=;j<degree;j++){

                ans+=G[i][j].w;

                minn=min(minn,G[i][j].w);

            }

            ans+=(ll)minn*(degree-);//当degree为1时与上面的ans相互消去

        }

        cout<<ans<<endl;

    }

    return ;

}