CF101D.Castle

Gerald is positioned in an old castle which consists of n halls connected with n - 1 corridors. It is exactly one way to go from any hall to any other one. Thus, the graph is a tree. Initially, at the moment of time 0, Gerald is positioned in hall 1. Besides, some other hall of the castle contains the treasure Gerald is looking for. The treasure's position is not known; it can equiprobably be in any of other n - 1 halls. Gerald can only find out where the treasure is when he enters the hall with the treasure. That very moment Gerald sees the treasure and the moment is regarded is the moment of achieving his goal.

The corridors have different lengths. At that, the corridors are considered long and the halls are considered small and well lit. Thus, it is possible not to take the time Gerald spends in the halls into consideration. The castle is very old, that's why a corridor collapses at the moment when somebody visits it two times, no matter in which direction.

Gerald can move around the castle using the corridors; he will go until he finds the treasure. Naturally, Gerald wants to find it as quickly as possible. In other words, he wants to act in a manner that would make the average time of finding the treasure as small as possible. Each corridor can be used no more than two times. That's why Gerald chooses the strategy in such a way, so he can visit every hall for sure.

More formally, if the treasure is located in the second hall, then Gerald will find it the moment he enters the second hall for the first time — let it be moment _t_2. If the treasure is in the third hall, then Gerald will find it the moment he enters the third hall for the first time. Let it be the moment of time _t_3. And so on. Thus, the average time of finding the treasure will be equal to .

杰拉尔德位于一座古老的城堡中，该城堡由 $n$ 个大厅和 $n-1$ 条走廊组成。任意两个大厅之间恰好存在唯一一条路径。因此，该图是一棵树。初始时刻（时间 $0$），杰拉尔德位于第 $1$ 号大厅。此外，城堡中某个其他大厅藏有杰拉尔德正在寻找的宝藏。宝藏的具体位置未知；它等概率地出现在其余 $n-1$ 个大厅中的任意一个。杰拉尔德只有在进入藏有宝藏的大厅时，才能确定宝藏的位置。就在他首次进入该大厅的那一刻，他便看见了宝藏，此时刻即被视为他达成目标的时刻。

各走廊长度不同。由于走廊较长而大厅较小且光线充足，因此可忽略杰拉尔德在大厅内停留所花费的时间。城堡非常古老，因此每当有人以任意方向经过某条走廊两次时，该走廊便会立即坍塌。

杰拉尔德可通过走廊在城堡中移动，直至找到宝藏。显然，杰拉尔德希望尽快找到宝藏，即采取一种策略，使得找到宝藏的平均时间最小。每条走廊最多只能被使用两次，因此杰拉尔德所选择的策略必须确保他能够遍历所有大厅。

更形式化地，若宝藏位于第 $2$ 号大厅，则杰拉尔德将在他首次进入第 $2$ 号大厅的时刻找到宝藏——记该时刻为 $t_2$。若宝藏位于第 $3$ 号大厅，则杰拉尔德将在他首次进入第 $3$ 号大厅的时刻找到宝藏——记该时刻为 $t_3$。依此类推。于是，找到宝藏的平均时间为 。

The first line contains the only integer n (2 ≤ n ≤ 105) — the number of halls in the castle. Next n - 1 lines each contain three integers. The i-th line contains numbers a__i, b__i and t__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ t__i ≤ 1000) — the numbers of halls connected with the i-th corridor and the time needed to go along the corridor. Initially Gerald is in the hall number 1. It is guaranteed that one can get from any hall to any other one using corridors.

第一行包含唯一一个整数 $n$（$2 \leq n \leq 10^5$）——城堡中大厅的数量。接下来的 $n-1$ 行每行包含三个整数。第 $i$ 行包含整数 $a_i$、$b_i$ 和 $t_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq t_i \leq 1000$）——表示第 $i$ 条走廊所连接的两个大厅的编号，以及沿该走廊通行所需的时间。初始时，杰拉尔德位于编号为 $1$ 的大厅。保证通过走廊可以从任意一个大厅到达其他任意一个大厅。

Print the only real number: the sought expectation of time needed to find the treasure. The answer should differ from the right one in no less than 10 - 6.

输出唯一的实数：找到宝藏所需时间的期望值。答案与正确结果的绝对误差不应超过 $10^{-6}$。

In the first test the castle only has two halls which means that the treasure is located in the second hall. Gerald will only need one minute to go to the second hall from the first one.

In the second test Gerald can only go from the first hall to the third one. He can get from the third room to the first one or to the second one, but he has already visited the first hall and can get nowhere from there. Thus, he needs to go to the second hall. He should go to hall 4 from there, because all other halls have already been visited. If the treasure is located in the third hall, Gerald will find it in a minute, if the treasure is located in the second hall, Gerald finds it in two minutes, if the treasure is in the fourth hall, Gerald will find it in three minutes. The average time makes 2 minutes.

In the third test Gerald needs to visit 4 halls: the second, third, fourth and fifth ones. All of them are only reachable from the first hall. Thus, he needs to go to those 4 halls one by one and return. Gerald will enter the first of those halls in a minute, in the second one — in three minutes, in the third one - in 5 minutes, in the fourth one - in 7 minutes. The average time is 4 minutes.

在第一个测试中，城堡仅有两个大厅，这意味着宝藏位于第二个大厅。杰拉尔德只需一分钟即可从第一个大厅到达第二个大厅。

在第二个测试中，杰拉尔德只能从第一个大厅前往第三个大厅。他可以从第三个大厅前往第一个或第二个大厅，但他已经访问过第一个大厅，而从第一个大厅无法再前往任何其他大厅。因此，他必须前往第二个大厅。接着，他应从第二个大厅前往第四大厅，因为其余所有大厅都已被访问过了。如果宝藏位于第三个大厅，杰拉尔德将在一分钟内找到它；如果宝藏位于第二个大厅，他将在两分钟内找到它；如果宝藏位于第四大厅，他将在三分钟内找到它。平均耗时为 2 分钟。

在第三个测试中，杰拉尔德需要访问四个大厅：第二个、第三个、第四个和第五个大厅。而这四个大厅均仅能从第一个大厅抵达。因此，他必须依次访问这四个大厅并返回。杰拉尔德将在一分钟内进入这四个大厅中的第一个，在三分钟内进入第二个，在五分钟内进入第三个，在七分钟内进入第四个。平均耗时为 4 分钟。