Description

You are given a tree with $n$ nodes, rooted at $1$, with edge weights. Define the path length $d(u,v)$ between two nodes $u, v$ on the tree as the sum of edge weights along the path from $u$ to $v$.

For an unordered pair $(u,v)$, define a "tree triangle" if and only if all of the following hold:

• Let $w$ be the lowest common ancestor of $u, v$. Then $w\neq u$ and $w\neq v$.
• Using $d(u,w)$, $d(v,w)$, and some positive integer $x$ as side lengths, a triangle can be formed. The value $x$ can be chosen arbitrarily, so a pair $(u,v)$ may produce multiple tree triangles.

In this case, $d(u,w)+d(v,w)+x$ is called the size of this tree triangle. See the sample explanation for a concrete example.

Two tree triangles are considered different if at least one of the following conditions holds:

• The unordered pair $(u,v)$ is different.
• The size of the tree triangle is different.

For a weighted tree $T$, define its sine value $\sin T$ as the ratio of:

• the sum of sizes of all tree triangles in $T$,

to

• the total number of distinct tree triangles in $T$.

Little H gives you $T$ and wants you to compute $\sin T$. To avoid precision issues, output the result modulo $10^9+7$. In particular, if there are no tree triangles in $T$, then $\sin T=0$.

Input Format

The first line contains a positive integer $n$, the number of nodes in the tree.

The next $n-1$ lines each contain three positive integers $u, v, w$, indicating that there is an edge of weight $w$ between nodes $u$ and $v$.

Output Format

Output one line: the value of $\sin T$ modulo $10^9+7$. The testdata guarantees that the total number of distinct tree triangles in $T$ is not a multiple of $10^9+7$.

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

214285725

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

662721928

Hint

Sample Explanation

For sample 1, $T$ is shown in the figure below.

The triangle cycles formed by nodes $1,2,3$ are: $\underline{2,3},2;~\underline{2,3},3;~\underline{2,3},4$.

The triangle cycles formed by nodes $1,3,4$ are: $\underline{3,3},1;~\underline{3,3},2;~\underline{3,3},3;~\underline{3,3},4;~\underline{3,3},5$.

The triangle cycles formed by nodes $1,3,5$ are: $\underline{3,4},2;~\underline{3,4},3;~\underline{3,4},4;~\underline{3,4},5;~\underline{3,4},6$.

The triangle cycle formed by nodes $2,4,5$ is: $\underline{1,2},2$.

Sum of all triangle cycle sizes: $(7+8+9)+(7+8+\dots+11)+(9+10+\dots+13)+5=129$.

Total number of triangle cycles: $3+5+5+1=14$.

$\sin T=\dfrac{129}{14}$, and the result modulo $10^9+7$ is $214285725$.

Constraints

This problem uses bundled testdata.

• Special Property A: There exists a node in $T$ with degree $n-1$.
• Special Property B: Except for leaf nodes, every node has degree $2$.
• Special Property C: $T$ is a perfect binary tree.

For all testdata, $1\le n\le 10^5$ and $1\le w\le 10^9$.

Notes

In the attached file depression_sample.zip:

• depression_sample1.in is sample #1.
• depression_sample2.in satisfies Special Property A.
• depression_sample3.in satisfies Special Property B.
• depression_sample4.in satisfies Special Property C.
• depression_sample5.in does not satisfy any special property.

Translated by ChatGPT 5