Be a human first

The motto of Songdo High School is "Be a human first."

Dohun, who entered Songdo High School the year before last, read this motto carved on a rock on his way to school. He took it literally to mean that he should become a real human, so he started looking for the best garlic and mugwort to eat for 100 days.

This is the rock with the motto, photographed at the front gate of Songdo High School in winter 2021.

First, Dohun spent two and a half years comparing garlic from around the world and found the best one. Now only the mugwort was left to choose. But Dohun had planned to eat garlic and mugwort for 100 days and become a human before graduation. After choosing the garlic, very little time was left!

Mugwort can be represented as a tree with $n$ vertices and $n-1$ weighted edges. The value of the mugwort tree is defined as follows.

• For each simple path, the taste is the sum of the edge weights on the path.
• For each simple path, the aroma is the maximum edge weight on the path.
• The value of the mugwort is the sum, over all simple paths containing at least one edge, of taste multiplied by aroma.
• The direction of a simple path is not considered.

Write a program that computes the value of the given mugwort so that Dohun can choose the mugwort quickly. Since the value can become very large, print it modulo $10^9+7$.

The first line contains the number of vertices $n$.

Each of the next $n-1$ lines contains integers $u$, $v$, and $w$, meaning that an edge connects $u$ and $v$ and has weight $w$.

Print the value of the mugwort modulo $10^9+7$.

• $2 \le n \le 200\,000$.
• $1\le u, v\le n$.
• For each $(u,v,w)$ triple, $u\neq v$.
• $1\le w\le 10^9$.
• The given graph is guaranteed to be a tree.

• A tree is a connected graph with no cycles.
• In a tree, a simple path is the path between two vertices that uses the fewest edges.