P7980 [JRKSJ R3] a question

This is a question.

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)$.

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 one integer representing the answer. Since the answer can be very large, output it modulo $10^9+7$.

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 | $\text{Subtask}$ | $n\le$ | Special Property | Score | Dependencies | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^3$ | None | $10$ | None | | $2$ | $10^4$ | None | $20$ | $1$ | | $3$ | $2\times 10^6$ | The tree is a star | $20$ | None | | $4$ | $2\times 10^6$ | The tree is a chain | $20$ | None | | $5$ | $2\times 10^6$ | None | $30$ | $1,2,3,4$ | 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