Helen 和 Henry 是 Hiddenland 非常受欢迎的电视节目“隐藏迷宫”（Hidden Maze）的粉丝。在这个节目中，两名参赛者（通常是一对已婚夫妇）在由 $n$ 个大厅和若干隧道组成的迷宫中穿行。每条隧道连接两个不同的大厅，且任意两个大厅之间最多只有一条隧道。

节目开始时，两名参赛者被放置在两个不同的大厅中。他们需要尽快移动以在时间耗尽前相遇。为了通过每条隧道，参赛者需要找到一条写有正整数的纸条，即线索。

如果参赛者在时间耗尽前最终在某条隧道中相遇，并且成功找到了他们相遇隧道中的线索，他们就被视为获胜者。奖金的价值计算方式是：将他们找到的所有线索按数值排序，并取其中位数。游戏设置总是保证他们找到的线索数量为奇数。

Helen 和 Henry 看过很多期节目，现在他们对节目的机制非常了解。他们注意到迷宫在不同期节目之间不会改变，并绘制了迷宫的完整地图。不久之后，Helen 和 Henry 发现迷宫的建造方式使得如果你访问任何隧道最多一次，那么任意两个大厅之间有且仅有一条路径。

Helen 和 Henry 一直很好奇这个伟大的迷宫是如何建造的，不久前他们看到了一次对 Hillary 的采访，她曾在建造迷宫的公司工作。Hillary 说，为了保证节目的公平性，迷宫是使用以下随机算法创建的：

1. 选择大厅数量 $n$。建造编号从 $1$ 到 $n$ 的 $n$ 个大厅。
2. 随机选择两个整数 $i$ 和 $j$，每个整数在 $1$ 到 $n$ 之间均匀分布。
3. 如果大厅 $i$ 和 $j$ 相同，或者它们之间已经通过隧道连通，则返回第 2 步。
4. 在 $i$ 和 $j$ 之间建造隧道。如果此时任意两个大厅之间都有路径相连，则停止过程，否则返回第 2 步。

Helen 和 Henry 还注意到，每条隧道包含且仅包含一个线索，且其数值在不同期节目中从不改变。然而，他们不知道生成线索数值的算法。Helen 和 Henry 在他们的地图上记录了每条隧道的线索数值。

找到线索并穿过隧道从一个大厅到达另一个大厅总是需要 1 分钟。当参赛者在隧道末端相遇时，从大厅跑到隧道中心需要 0.5 分钟。给予参赛者的时间仅在他们采取最优行动时才足够相遇，即他们沿着最短路径跑向对方，在寻找线索时从不犯错，也从不转入不属于最短路径的其他隧道。为了让参赛者在某条隧道的中心相遇，他们在节目开始时被放置的位置使得他们之间最短路径的长度为奇数。

Helen 和 Henry 想参加这个节目。他们对迷宫了如指掌，并且非常确信他们能够成功地以最优方式移动并及时找到所有线索。假设初始大厅对是从所有最短路径长度为奇数的对中均匀随机选择的，他们需要知道他们赢得奖金的期望值。你的任务是帮助他们计算这个期望值。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 30\,000$)，表示大厅的数量。接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i, c_i$ ($1 \le u_i, v_i \le n, 1 \le c_i \le 10^6$)，描述连接大厅 $u_i$ 和 $v_i$ 的第 $i$ 条隧道，其中包含数值为 $c_i$ 的线索。迷宫总是由题目描述中的随机算法创建。

输出格式

输出一个实数，表示奖金的期望值。答案的绝对误差或相对误差不得超过 $10^{-9}$。

样例

样例输入 1

2
2 1 1

样例输出 1

1

样例输入 2

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

样例输出 2

3.50

样例输入 3

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

样例输出 3

3.1666666667