基因树（gene tree）是一种展示各种基因或生物物种演化过程的树。基因树代表了存储在叶节点上的特定基因之间的相关性，且不对其祖先关系做任何假设。叶节点代表基因，称为分类单元（taxa），内部节点代表假定的祖先分类单元。树中的每条边都关联一个正整数，即系统发育长度（phylogenetic length），它量化了边两端节点之间的演化距离。例如，下图左侧展示了一个具有六个叶节点的基因树，它近似表示了六个分类单元之间的关系；右侧展示了一个具有四个分类单元的基因树。

图 B.1：无根基因树 $T_1$ 和 $T_2$。

像上面的树 $T_1$ 和 $T_2$ 一样，基因树被建模为无根树，其中每个内部节点（非叶节点）的度数为三。两个叶节点之间的路径长度是它们之间唯一路径上所有边的系统发育长度之和。在 $T_1$ 中，Human 和 Cow 之间的路径长度为 $2 + 3 = 5$，Human 和 Goldfish 之间的路径长度为 $2 + 4 + 8 + 10 = 24$。这些长度表明，从遗传学角度来看，Human 与 Cow 的亲缘关系比与 Goldfish 的亲缘关系更近。从 $T_2$ 中，我们可以推测与 Human 亲缘关系最近的灵长类动物是 Chimpanzee。

研究人员对测量树中基因之间的距离很感兴趣。一种著名的距离度量是所有无序叶节点对的路径长度平方和。更准确地说，这样的距离 $d(T)$ 定义如下：

$$d(T) = \sum_{\text{无序对 } (u, v)} p_{u, v}^2$$

其中 $p_{u, v}$ 是 $T$ 中两个叶节点 $u$ 和 $v$ 之间的路径长度。注意，$d(T)$ 是 $T$ 中所有无序叶节点对 $u$ 和 $v$ 的路径长度 $p_{u, v}$ 的平方和。对于图 B.1 中的基因树 $T_2$，共有六条路径，对应所有无序叶节点对：(Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan) 和 (Gorilla, Orangutan)。路径长度的平方和为 $2^2 + 4^2 + 5^2 + 4^2 + 5^2 + 5^2 = 111$，因此 $d(T_2) = 111$。

给定一棵无根基因树 $T$，编写一个程序输出 $d(T)$。

输入格式

程序从标准输入读取数据。输入的第一行包含一个整数 $n$ ($4 \le n \le 100,000$)，其中 $n$ 是输入基因树 $T$ 的节点数。$T$ 有 $n - 1$ 条边。$T$ 的节点编号从 $1$ 到 $n$。接下来的 $n - 1$ 行表示 $T$ 的 $n - 1$ 条边，每行包含三个非负整数 $a$、$b$ 和 $l$ ($1 \le a \neq b \le n, 1 \le l \le 50$)，表示节点 $a$ 和 $b$ 之间形成一条系统发育长度为 $l$ 的边。

输出格式

程序将结果写入标准输出。输出仅一行，包含一个正整数 $d(T)$。

样例

样例输入 1

4
1 4 1
4 3 1
2 4 1

样例输出 1

12

样例输入 2

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

样例输出 2

111

样例输入 3

10
1 2 10
10 2 7
3 2 8
3 9 3
9 8 2
7 9 1
6 4 3
4 5 2
3 4 4

样例输出 3

4709