题目描述

这是问题的简单版本。在这个版本中 $n\leq10^4$。

阿兔和他的兔子伙伴们居住在一个由多个兔子窝组成的兔子洞中。这个兔子洞的结构是一棵树，其中：

• 每个节点代表一个兔子窝
• 每条边代表连接两个兔子窝的通道，并有一个距离 $z$

阿兔打算随机选择一个兔子窝作为仓库（所有兔子窝被选中的概率均等）。请你计算这个仓库到所有其他兔子窝的距离之和的期望值。

输入格式

第一行包含一个正整数 $n$ $(1 \leq n \leq 10^4)$，表示兔子窝的数量。

接下来 $n-1$ 行，每行包含三个正整数 $x, y, z$ $(1 \leq x, y \leq n, 1 \leq z \leq 10^9)$，表示兔子窝 $x$ 和 $y$ 之间有一条长度为 $z$ 的通道。

输出格式

输出一个整数，表示期望值。

注意：由于答案可能很大，请输出其对 $10^9 + 7$ 取模后的结果。

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

20