Cost

You are given an undirected graph whose edges have distinct positive weights. The vertices are numbered from 1 to N.

For two distinct vertices u and v, define Cost(u, v) as the sum of the weights of the edges removed by the following process.

1. If there is a path between u and v in the current graph, remove the remaining edge with the smallest weight from the current graph.
2. Repeat step 1 until there is no path between u and v.

The following figure shows one graph with 6 vertices.

For vertices 2 and 6, the process removes the edges (2, 3), (4, 5), (3, 5), (3, 4), and (2, 6) in that order. After edge (2, 6) is removed, no path remains between the two vertices, so the process stops. Therefore Cost(2, 6) = 2 + 3 + 4 + 5 + 6 = 20.

Given the graph, compute the total of Cost(u, v) over all vertex pairs (u, v) such that u < v. If the total is at least 10^9, output the remainder after dividing it by 10^9.

The first line contains two integers N (1 < N <= 100,000) and M (1 <= M <= 100,000), the number of vertices and the number of edges.

Each of the next M lines contains three positive integers x, y, and w, describing an edge between vertices x and y with weight w. All edge weights are distinct, and 1 <= w <= 100,000.

Print the total of Cost(u, v) over all vertex pairs (u, v) such that u < v. If the total is at least 10^9, print the remainder after dividing it by 10^9.