Roads#8257
In the country of Olympia, there are cities connected by roads. Each road has a distinct length, which is a power of two: from 2^0 up to 2^{M-1}. Your task is to calculate the sum of all shortest distances between every pair of cities, and present the result in binary form.
The first line contains two integers, and .
Each of the following lines describes a road with three integers , , and , meaning there is a bidirectional road of length 2^C between cities and .
Here 1 \leq A, B \leq N, and 0 \leq C \leq M - 1.
Each road length is unique. It is guaranteed that the graph is connected and properly defined.
Print the sum of the shortest distances between all pairs of cities in binary form. The result may be very large.
مثال 1
For better understanding, consider drawing the graph.
Example distances:
From city 1 to city 2: 2^0
From city 1 to city 3: 2^0 + 2^2
From city 1 to city 4: 2^0 + 2^2 + 2^1
From city 2 to city 3: 2^2
From city 2 to city 4: 2^2 + 2^1
From city 3 to city 4: 2^1
Total sum: 3 \times 2^0 + 3 \times 2^1 + 4 \times 2^2 = 2^0 + 2^3 + 2^4 = \text{11001[2]}