Gene Tree

A gene tree is a tree that shows the evolution of various genes or biological species. A gene tree represents the relatedness of specific genes stored at the leaf nodes, without any assumption about their ancestry. Leaf nodes represent genes, called taxa, and internal nodes represent putative ancestral taxa. Each edge in the tree has a positive integer, the phylogenetic length, which quantifies the evolutionary distance between the two nodes of the edge. For example, the left figure below shows a gene tree with six leaf nodes, which approximates the relation among six taxa, and the right one shows a gene tree with four taxa.

Figure B.1: Unrooted gene trees T1 and T2.

Like the trees T1 and T2 above, gene trees are modeled as unrooted trees in which every internal node (non-leaf node) has degree three. A path-length between two leaf nodes is the sum of the phylogenetic lengths of the edges along the unique path between them. In T1, the path-length between Human and Cow is 2 + 3 = 5 and the path-length between Human and Goldfish is 2 + 4 + 8 + 10 = 24. These lengths indicate that Human is much closer to Cow than to Goldfish genetically. From T2, we can guess that the primate closest to Human is Chimpanzee.

Researchers are interested in measuring the distance between genes in the tree. A famous distance measure is the sum of squared path-lengths over all unordered leaf pairs. More precisely, such a distance d(T) is defined as follows:

[d(T) = \sum_{\text{unordered pair } (u, v)}{p^2_{u, v}}]

where p**u,v is a path-length between two leaf nodes u and v in T. Note that d(T) is the sum of the squared path-lengths p2u,v over all unordered leaf pairs u and v in T. For the gene tree T2 in Figure B.1, there are six paths over all unordered leaf pairs, (Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan), and (Gorilla, Orangutan). The sum of squared path-lengths is 22 + 42 + 52 + 42 + 52 + 52 = 111, so d(T2) = 111.

Given an unrooted gene tree T, write a program to output d(T).

Your program is to read from standard input. The input starts with a line containing an integer n (4 ≤ n ≤ 100,000), where n is the number of nodes of the input gene tree T. Then T has n − 1 edges. The nodes of T are numbered from 1 to n. The following n − 1 lines represent the n − 1 edges of T, where each line contains three non-negative integers a, b, and l (1 ≤ a ≠ b ≤ n, 1 ≤ l ≤ 50), where two nodes a and b form an edge with phylogenetic length l.

Your program is to write to standard output. Print exactly one line. The line should contain one positive integer d(T).