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

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 64MB Input: Output:

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 NN cities and MM direct roads. A direct road between two cities aa and bb is represented by an edge and has a length dd. 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)d(i, j) is the sum of the lengths of the critical roads on the direct or indirect route from city ii to city jj.

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:

S=i=1N1j=i+1Nd(i,j)\displaystyle S = \sum_{i=1}^{N-1} \sum_{j = i + 1}^N d(i,j)

The sum can be very large, so Marcel will be satisfied with finding the remainder when divided by 109+710^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 NN and MM, the number of cities and the number of direct roads between the NN cities, respectively. Then follow MM lines with 3 values separated by a space: aa, bb, and dd, indicating that there is a direct road of length dd between cities aa and bb.

Output data

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

Constraints and clarifications

  • 2N200 0002 \leq N \leq 200 \ 000;
  • 1Mmin(200 000,N(N1)2)1 \leq M \leq \min(200 \ 000, \frac{N \cdot (N-1)}{2});
  • 1d1091 \leq d \leq 10^9, where dd is the length of a direct road.
# Points Constraints
0 0 Examples
1 6 N100N \leq 100
2 12 N1 000N \leq 1\ 000 and the network is a tree
3 34 The network is a tree
4 48 No additional constraints

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 network in the example\text{The network in the example}

The sum SS includes contributions from:

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

In this example, d(3,5)=d(3,6)=d(5,6)=0d(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

Log in or sign up to be able to send submissions!