- All Contests
- HourRank 16
- Magic Number Tree

# 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:

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:

.

- .
- .
- .

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