D. [L2-4]拜树年

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

食肉斯特是一只土拨鼠!

只食肉斯特,他们居住的地方构成了一棵树。某一天,食肉斯特们不约而同地决定拜访其他人的住所。在拜访其他人住所的过程中,他们产生了一个问题:

如果所有人都从自己住所出发,拜访其他人的住所,每一次拜访都要从自己家出发,拜访完一处后就要回家,所有人拜访完所有住所所经过的边的和是多少。

你能帮食肉斯特们解决这个问题吗?

形式上来说,令 表示 点和 点之间的最短路径包含的边权和,求

: 由 个点 条边形成的连通图。

输入格式

第一行1个正整数 。表示 个点。

接下来 行输入三个正整数 , , 表示每条边的起点,终点,边权。

输出格式

输出一个正整数表示答案。

样例

样例输入

4
1 2 1
1 3 2
2 4 4

样例输出

88

数据范围与提示

样例解释

对于样例2,每两个点之间的最短路径长度如下表格所示:

#1 #2 #3 #4
#1 0 1 2 5
#2 1 0 3 4
#3 2 3 0 7
#4 5 4 7 0

对于 的数据,满足