题目描述

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

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

输入格式

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

接下来 \(N-1\) 行三个整数 \(S_i, T_i, D_i\)；描述一条边（\(S_i, T_i\)）权值为 \(D_i\)；

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

输出格式

输出仅一个数，表示最小的完全图 \(G\) 的边权和。

样例数据

样例输入

4  
1 2 1  
1 3 1  
1 4 2  

样例输出

12

样例说明

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

限制与提示

对于 \(20\%\) 的数据，\(N\le 10\)；

对于 \(50\%\) 的数据，\(N\le 1000\)；

对于 \(100\%\) 的数据，\(N\le 10^5, 1\le D_i\le 10^5\)。