Explorer's Birthday
Tag(s):

Algorithms, Medium

Problem
Editorial
Analytics

Today is Explorer's birthday, and two of his best friends Raful and Jambo gave him a tree with $N$ vertices and $N-1$ edges. After playing with it for a while, Explorer got bored, so Raful and Jambo gave him a task:

find the answer $A$ modulo $10^9 + 7$ - sum of all functions $f(u, v)$ for all unordered pairs of vertices $(u, v)$ such that $u != v$. The function $f(u ,v)$ is the product of the weights of the edges on the shortest path between $u$ and $v$. Note that pairs $(u, v)$ and $(v, u)$ are considered the same, so must only be counted once.

He easily solved it. Can you (the best programmer in Lalalandia) do it too?

Input format

The first line contains one integer $N$ - the number of vertices.

The next $N-1$ lines describe the edges: each contains three integers $u$, $v$ and $c$. This means that there is the edge with weight $c$ between vertices $u$ and $v$.

Output format

The first line should contain the single integer $A$ modulo $10^9 +7$ - sum of all functions $f(u, v)$.

Constraints:

$1 \le N \le 5 * 10^5$

$1 \le u, v \le N$

$1 \le c \le 10^9$

SAMPLE INPUT
4
1 2 2
2 3 3
1 4 1
SAMPLE OUTPUT
20

Explanation

There are $6$ unordered unique pairs: $(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)$, so the answer is $2 + 6 + 1 + 3 + 2 + 6 = 20$.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Math > Linear Algebra
• Math > Number Theory
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Algorithms > String Algorithms