'''
算法思路
在克鲁斯卡尔构建最小生成树增加长度为w的一条边连接两个连通分量的同时，将两个连通分量
中的点对全部用w+1的权值的边连接起来，最后的完全图的总边权和就是最小的, 克鲁斯卡尔
算法迭代过程中累加长度是w+1的边权即可
'''

class MergeSetExt:
    def __init__(self, max_key_val = 0, trans_key_func=None):
        if trans_key_func is not None and max_key_val > 0:
            # 如果能够提供转换key的回调，并查集内部用线性表存储
            self.trans_key_callback = trans_key_func
            self.m = [-1 for _ in range(max_key_val+1)]
            self.__root2cluster_size = [0 for _ in range(max_key_val+1)]
        else:
            # 如果不能提供转换key的回调，并查集内部用hash表存储
            self.trans_key_callback = None
            self.m = {}
            self.__root2cluster_size = {}
        self.__root_cnt = 0

    def getRoot(self, node):
        buf = []
        root = self.trans_key_callback(node) if self.trans_key_callback else node
        while self.m[root] != root:
            buf.append(root)
            root = self.m[root]
        for key in buf:
            self.m[key] = root

        return root

    def merge(self, a, b):
        orig_a, orig_b = a, b
        if self.trans_key_callback:
            a, b = self.trans_key_callback(a), self.trans_key_callback(b)

        for node in [a, b]:
            if (self.trans_key_callback is None and node not in self.m) or (self.trans_key_callback is not None and self.m[node] == -1):
                self.m[node] = node
                self.__root2cluster_size[node] = 1
                self.__root_cnt += 1

        root1 = self.getRoot(orig_a)
        root2 = self.getRoot(orig_b)
        if root1 != root2:
            self.m[root1] = root2

            self.__root2cluster_size[root2] += self.__root2cluster_size[root1]
            if self.trans_key_callback:
                self.__root2cluster_size[root1] = 0
            else:
                self.__root2cluster_size.pop(root1)
            self.__root_cnt -= 1

    # 根据根节点的数值获取其所在的簇的大小
    def getClusterSize(self, root):
        return self.__root2cluster_size[root]

    def isInSameSet(self, a, b):
        if a == b:
            return True

        orig_a, orig_b = a, b
        if self.trans_key_callback:
            a, b = self.trans_key_callback(a), self.trans_key_callback(b)

            for node in [a, b]:
                if self.m[node] == -1:
                    return False
        else:
            for node in [orig_a, orig_b]:
                if node not in self.m:
                    return False

        return self.getRoot(orig_a) == self.getRoot(orig_b)

    def getRootNum(self):
        return self.__root_cnt

    def getClusters(self):
        rec = {}
        if self.trans_key_callback is None:
            for node in self.m:
                root = self.getRoot(node)
                if root not in rec:
                    rec[root] = []
                rec[root].append(node)
        else:
            for node in range(len(self.m)):
                if self.m[node] == -1:
                    continue

                root = self.getRoot(node)
                if root not in rec:
                    rec[root] = []
                rec[root].append(node)

        return [nodes for nodes in rec.values()]


def getMinSpanTreeKruscal(edges, node_num):
    if len(edges) == 0:
        return [None, None]


    edge_list = [(w, a, b) for a, b, w in edges]
    edge_list.sort()

    merge_set = MergeSetExt(max_key_val=node_num, trans_key_func= lambda x: x)
    for node in range(1, node_num+1):
        merge_set.merge(node, node)

    sum = 0
    edge_cnt = 0
    for w, a, b in edge_list:
        if merge_set.isInSameSet(a, b):
            continue

        # 获取a, b所在连通分量的所有节点，两个连通分量之间的点出了a, b以外全部
        # 连接起来，边权是w+1
        root_a, root_b = merge_set.getRoot(a), merge_set.getRoot(b)
        cnt1, cnt2 = merge_set.getClusterSize(root_a), merge_set.getClusterSize(root_b)
        sum += (cnt1 * cnt2 - 1) * (w+1)

        merge_set.merge(a, b)
        edge_cnt += 1

        if edge_cnt == node_num - 1:
            break

    return sum

t = int(input())
for _ in range(t):
    n = int(input())
    edges = []
    for i in range(n-1):
        a, b, w = map(int, input().split())
        edges.append((a,b,w))

    print(getMinSpanTreeKruscal(edges, node_num=n))