Background

This is a question.

Problem Description

Now there is a tree $\text{T}$ with $n$ nodes. The edges are weighted, and the node labels form a permutation of $[1,n]$.

Let $\text{G}$ be the complement graph of $\text{T}$. For each edge $(x,y)$ in $\text{G}$, its weight is the sum of edge weights along the path $x\rightarrow y$ in $\text{T}$.

Let $dis(x,y)$ be the length of the shortest path between nodes $x$ and $y$ in $\text{G}$. If $x$ and $y$ are not connected, define $dis(x,y)=0$.

Compute $\displaystyle\sum_{i=1}^{n-1} \sum_{j=i+1}^n dis(i,j)$.

Input Format

All numbers in the input are integers.

The first line contains one integer $n$.
The next $n-1$ lines each contain three integers $u,v,w$, indicating that there is an edge in $\text{T}$ connecting $u$ and $v$ with weight $w$.

Output Format

Output one integer representing the answer. Since the answer can be very large, output it modulo $10^9+7$.

3
1 2 2
2 3 3

5

4
1 2 4
2 3 4
3 4 4

96

Hint

The complement graph $\text{G}$ of $\text{T}$ is defined as follows: for an edge $(x,y)(1\le x,y\le n,x\ne y)$, if this edge does not exist in $\text{T}$, then it exists in $\text{G}$; if this edge exists in $\text{T}$, then it does not exist in $\text{G}$. $\text{G}$ is an undirected graph.

Sample Explanation

For sample $2$, the graph $\text{G}$ is shown in the figure:

We have: | $dis(i,j)$ | $j=1$ | $j=2$ | $j=3$ | $j=4$ | | :----------: | :----------: | :----------: | :----------: | :----------: | | $i=1$ | | $20$ | $8$ | $12$ | | $i=2$ | | | $28$ | $8$ | | $i=3$ | | | | $20$ |

So the answer is $96$.

Constraints

For $100\%$ of the testdata, $2\le n \le 2\times 10^6$, $1\le x,y\le n$, $0\le v\le 10^9$.

The input file for this problem is large. Please use an appropriate fast input method.

Translated by ChatGPT 5