Tree Distance 2

题号：NC305938
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一棵 $n$ 个点的有根树，第 $i$ 条边的边权 $w_i$ 为 $[l_i,r_i]$ 中的整数。根节点编号为 $1$ 。
定义一个节点是叶子当且仅当它没有子节点，你需要选择一组 $w_i$ 使得根节点到每个叶子的简单路径边权和均相等。在此限制下最小化 $\sum w_i$ 。数据保证有解。
每个测试点中有多组测试数据。

输入描述:

第一行，一个整数 ，表示数据组数。
对于每组数据：
第一行，一个整数 。
接下来  行，第  行有三个整数 ，表示第  条边连接点  和点 ，且其边权  为  中的整数。

输出描述:

对于每组数据：
一行，一个整数，表示答案。

示例1

输入

复制

输出

复制

0
4
14

备注:

。