【 Description 】
小A和小B正在在x条走廊内玩追逐游戏，每条走廊只有末端会有房间，故一条走廊有两间屋子。小A觉得这很无聊，于是他决定叫更多的伙伴，在更多的走廊内一起玩追逐游戏。
现有n间屋子，小A会尽可能的找更多的人，但小A也不希望人太多，所以当走廊可以形成一个C++定义的完全图且走遍所有屋子的最短路线是最开始的走廊时，小A就不会叫人了。
同时，每条走廊的距离不同
【 Input 】
第一行一个正整数t，表示小A和小B一共玩了t次这种游戏
接下来t组：
第一行一个正整数n，表示一开始有n间屋子
接下来n-1行，每行三个正整数x，y，z。表示x号屋子和y号屋子之间的走廊是z米
【 Output 】
输出每t行
每行一个结果，表示该次游戏能添加的最多走廊的距离总米数
【 Sample Input 】
2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5
