James has a tree with $n$ nodes $n-1$ edges where the $i^{{th}}$ edge has a length, $w_i$. He wants to play a game involving $n$ moves. During each move, he performs the following steps:

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

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

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

James defines the magic number, $m$, as the sum of all numbers calculated in step $2$ of each move. Let $E_{m}$ be the expected value of $m$.

Give the tree's edges and their respective lengths, calculate and the print the value of $(E_m\times n!)\ \text{mod}\ (10^9+9)$. It is guaranteed that $E_m\times n!$ 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, $n$, denoting the number of nodes.

Each of the $n-1$ subsequent lines contains three space-separated integers describing the respective values of $u_i$, $v_i$, and $w_i$, meaning that there is an edge of length $w_i$ connecting nodes $u_i$ and $v_i$.

Constraints

$1\leq n\leq5000$
$1\leq u_i,v_i\leq n$
$1\leq w_i\leq10^9$

Subtasks

For $30\%$ of the max score $n\leq10$
For ${60\%}$ of the max score $n\leq400$

Output Format

Print a single integer denoting the value of $(E_m\times n!)\ \text{mod}\ (10^9+9)$.

Sample Input
3
2 1 2
3 2 3

Sample Output
50

Explanation

Let $d(u,v)$ be the distance between node ${u}$ and node ${v}$. Here are the ${6}$ different variants:

$(x_1,x_2,x_3)=(1,2,3)$

$(x_1,x_2,x_3)=(2,1,3)$

$(x_1,x_2,x_3)=(1,3,2)$. $m=7+3+0=10$

$(x_1,x_2,x_3)=(2,3,1)$. $m=0+5+0=5$
$(x_1,x_2,x_3)=(3,1,2)$. $m=2+0+8=10$
$(x_1,x_2,x_3)=(3,2,1)$. $m=0+2+8=10$

The expected value of the magic number is $E_m=\frac{50}{6}$. We then print the value of $(E_m\times n!)\ \text{mod}\ (10^9+9)=(\frac{50}{6}\times3!)\ \text{mod}\ (10^9+9)=50$.

见题面

见题面