dreaming3000之火星旅行

Time Limit: 5000 ms

Memory Limit: 65535 ms

Description

dreaming3000的xiaoyoulei有一天买了一张彩票,结果很不幸的事情发生了,他中奖了,可是对于这样的横财,dreaming3000有个不成文的规定,其他2个人也要分红,怎么办?怎么分?于是Bearjie 就提出来我们去火星旅游吧。于是他们准备去火星旅游了。 正如大家知道的,火星上是不能提供我们能生存的空气,所以旅游公司建了一些管道来连接这些旅游景点以便人工供氧,为了节省建造成本,旅游公司在建造时尽量建了少的管道,使得任意俩个景点能互相连通(可以经过其他的景点)。由于火星上的资源是全人类共有的,所以旅游公司不能收取景点的费用,当是他们能收取旅客们过管道的费用,不同的管道的费用可能不同。黑心的旅游公司为了赚更多的钱定下了一个规则:就是旅客不能往回走,当然可以在任意一个景点进入,任意一个景点出来。 贪恋的zlly一听说能去火星旅游,而且是吝啬的xiaoyoulei 出钱,于是想让xiaoyoulei多发费一些钱,可是zlly只能搞到旅游景点的地图,却不知道怎么旅游才能让xiaoyoulei多发钱,不过他听说NJUST的Acmer能过帮他解决这个问题,于是他向你们求救,你能告诉zlly能让xiaoyoulei 发费多少钱吗?

Input

第一行T,表示测试数据组数 每一组数据的第一行是一个 N(1 < = N< = 10^6),表示景点的个数. 接着有n-1行,每行有3个数a b c 表示(景点a到景点b之间)或(景点b到景点a之间)的管道收费是c (a不等于b , 1 < = a ,b < = n , 1 < = c < = 100) 保证任意2个景点是能连通的。

Output

对与每一个组测试数据,输出一行表xiaoyoulei最多会发费多少钱。

Sample Input

2
2
1 2 1
5
1 2 2
2 3 5
2 4 3
2 5 4

Sample Output

3
27

Hint

注意是dreaming3000 有3个人,都会去旅游的

Source

ZLLY

提交代码