RoAlgo Contest #11 - Back to School 2024 | Șanțuri și poduri

Marcel, a successful entrepreneur, owns a trucking company that operates transport services across the country. Facing resource allocation issues, he hired the firm "Ditches and Bridges" to analyze his transport network.

The experts modeled Marcel's network as a connected undirected graph with $N$ cities and $M$ direct roads. A direct road between two cities $a$ and $b$ is represented by an edge and has a length $d$. Between other cities, the road is indirect, being a simple path in the graph. A path is called simple if the edges do not repeat.

With this model in mind, the following observation was made: some direct roads are more critical than others. A direct road is critical if its removal would make it impossible to deliver goods between two or more cities. Thus, the following notation was made: $d(i, j)$ is the sum of the lengths of the critical roads on the direct or indirect route from city $i$ to city $j$.

Task

The experts now need to evaluate the importance of these critical roads, and since the company makes deliveries between all pairs of cities, they need to calculate the following sum:

The sum can be very large, so Marcel will be satisfied with finding the remainder when divided by $10^9 + 7$. As the young entrepreneur tends to make dubious financial decisions, you need to help the experts calculate this sum, as they are overwhelmed by the situation.

Input data

The first line contains $N$ and $M$, the number of cities and the number of direct roads between the $N$ cities, respectively. Then follow $M$ lines with 3 values separated by a space: $a$, $b$, and $d$, indicating that there is a direct road of length $d$ between cities $a$ and $b$.

Output data

On the first line, output a single integer, the required sum modulo $10^9 + 7$.

Constraints and clarifications

• $2 \leq N \leq 200 \ 000$;
• $1 \leq M \leq \min(200 \ 000, \frac{N \cdot (N-1)}{2})$;
• $1 \leq d \leq 10^9$, where $d$ is the length of a direct road.

Example 1

stdin

7 7
1 4 2
6 3 3
3 1 3
3 5 5
2 3 4
5 6 5
1 7 3

stdout

90

Explanation

The sum $S$ includes contributions from:

• $d(1,2) = 7$
• $d(1,3) = d(1,5) = d(1,6) = 3$
• $d(1,4) = 2$
• $d(1,7) = 3$
• $d(2,3) = d(2,5) = d(2,6) = 4$
• $d(2,4) = 9$
• $d(2,7) = 10$
• $d(3,4) = 5$
• $d(3,7) = 6$
• $d(4,5) = d(4,6) = d(4,7) = 5$
• $d(5,7) = d(6,7) = 6$

In this example, $d(3,5) = d(3,6) = d(5,6) = 0$ because no road between these pairs has a critical edge.

Example 2

stdin

8 8
7 6 17
2 1 10
6 2 5
2 5 19
3 1 5
1 8 4
7 2 1
5 4 18

stdout

567