Sin T over Tree Triangles

Given a tree with n nodes numbered from 1 to n (with the root being node 1) and weighted edges, define the distance d(u,v) between two nodes u and v as the sum of the weights on the unique path between them.

For an unordered pair (u, v) (with u and v distinct), let w be the lowest common ancestor (LCA) of u and v. We say that (u,v) produces a tree triangle if and only if:

• w ≠ u and w ≠ v.
• There exists a positive integer x such that the three lengths d(u,w), d(v,w) and x can form the sides of a triangle. Note that a different value of x will produce a different tree triangle.

Recall that three positive numbers a, b and c can form a triangle if and only if they satisfy the triangle inequalities:

$$a+b>c,\quad a+c>b,\quad b+c>a.$$

In our context, letting \(a=d(u,w)\) and \(b=d(v,w)\), the valid x are the positive integers satisfying

[ |a-b|< x < a+b. ]

Thus, the number of possible values for x is

[ \text{count} = (a+b-1) - (|a-b|) = 2\min(a,b)-1. ]

For each valid triangle arising from the pair (u,v) with a choice of x, its size is defined as $$d(u,w)+d(v,w)+x.$$

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

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

Finally, for the tree \(T\) the sin value \(\sin T\) is defined as the ratio between the sum of the sizes of all tree triangles in \(T\) and the total number of different tree triangles in \(T\). In formula, if \(S\) is the sum of sizes and \(C\) is the total count, then

$$\sin T = \begin{cases} \frac{S}{C} &\text{if } C>0,\\ 0 &\text{if } C=0. \end{cases}$$

Since the answer can be fractional, output \(\sin T\) modulo \(10^9+7\). That is, if \(\sin T\) is represented as a rational number \(\frac{S}{C}\), compute \(S \cdot C^{-1}\) modulo \(10^9+7\). (If there are no tree triangles then output 0.)

Note: For a given unordered pair \((u,v)\) with LCA \(w\), the two distances are \(a=d(u,w)\) and \(b=d(v,w)\). The valid integers x are those satisfying \(|a-b| < x < a+b\). For each such x, the triangle size is \(a+b+x\). In particular, the average size for the pair (when weighted evenly over all valid x) is

[ \frac{\sum_{x=|a-b|+1}^{a+b-1} (a+b+x)}{2\min(a,b)-1} = \frac{3(a+b)+|a-b|}{2}. ]

Your task is to compute \(\sin T\) modulo \(10^9+7\).

inputFormat

The first line contains a single integer n (number of nodes).

Each of the next n-1 lines contains three integers u, v and w, indicating there is an edge between nodes u and v with weight w.

outputFormat

Output a single integer: the value of \(\sin T\) modulo \(10^9+7\).

sample

3
1 2 1
1 3 2

5