对于完全图 G，若有且仅有一棵最小生成树为 T，则称完全图 G 是树 T 扩展出的。

给你一棵树 T，找出 T 能扩展出的边权和最小的完全图 G。

第一行 N 表示树 T 的点数；

接下来 N-1 行三个整数 Si, Ti , Di；描述一条边 (Si, Ti ) 权值为 Di；

保证输入数据构成一棵树。

样例说明

添加 D(2,3)=2, D(3,4)=3, D(2,4)=3 即可。

对于 20% 的数据，N ≤ 10；
对于 50% 的数据，N ≤ 1000；
对于 100% 的数据，N ≤ 10^5 , 1 ≤ Di ≤ 10^5。