We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Probability
  4. Magic Number Tree

Magic Number Tree

James has a tree with nodes edges where the edge has a length, . He wants to play a game involving moves. During each move, he performs the following steps:

  • Randomly chooses some node from the tree. Each node has an equal probability of being chosen.
  • Calculates the distance from node to each node reachable from using one or more edges.
  • Deletes node .

For example, the diagram below shows what happens when we choose a random node and delete it from the tree:

image

After moves, the tree is empty and the game ends.

James defines the magic number, , as the sum of all numbers calculated in step of each move. Let be the expected value of .

Give the tree's edges and their respective lengths, calculate and the print the value of . It is guaranteed that is an integer.

Note

Due to a bug in the system, you might see accepted verdict in this problem even if you don't pass all the test cases. Please ignore that verdict, only the score you get is important in the ranklist.

Input Format

The first line contains an integer, , denoting the number of nodes.
Each of the subsequent lines contains three space-separated integers describing the respective values of , , and , meaning that there is an edge of length connecting nodes and .

Constraints

Subtasks

  • For of the max score
  • For of the max score

Output Format

Print a single integer denoting the value of .

Sample Input

3
2 1 2
3 2 3

Sample Output

50

Explanation

Let be the distance between node and node . Here are the different variants:

  1. image

  2. image

  3. .

  4. .
  5. .
  6. .

The expected value of the magic number is . We then print the value of .