20263번 - Optimization for UltraNet 다국어

The UltraNet company provides network connectivity for all cities in a country. For a pair of cities, they are either directly connected or indirectly connected. A city i and another city j are directly connected if a cable with a symmetrical bandwidth of b_i,j = b_j,i is wired between them. For two cities that are not directly connected, at least one path between the two cities exists. In the current UltraNet, more than one path is possibly available for a city pair.

The current UltraNet is perfectly working, while the maintenance fee of each cable is costly. Energy conservation is another concern. The energy consumption of a cable is proportional to its bandwidth. Therefore, the company has an optimization plan to reorganize the network with the policies in the following order:

1. The number of cables should be minimized without sacrificing the connectivity of the whole UltraNet. In other words, exactly one path between every city pair should be satisfied.
2. If there is more than one way to minimize the number of cables, the bottleneck of the whole network should be maximized. The bottleneck of a network is determined by the city pair with the narrowest bandwidth, and the bandwidth of a city pair (i, j), b'_i,j, is determined by the cable with the narrowest bandwidth on the only path from i to j.
3. If there is still more than one way to meet the above two points, the total energy consumption of the network should be minimized. In other words, the sum of bandwidths of the remaining cables should be minimized.

Your task is to help UltraNet optimize the network and then output the sum of the bandwidths among all city pairs in the optimized network. For optimizing the following example, the three cables in dotted will be discarded. In the resulting network, the bottleneck is 3, the sum of bandwidths of the remaining four cables is 6 + 3 + 8 + 4 = 21, and the sum of the bandwidths among all city pairs is \(\sum_{i=1}{^n-1}\sum_{j=i+1}^{n}\)b'_i,j = 6 + 4 + 6 + 3 + 4 + 8 + 3 + 4 + 3 + 3 = 44.

Each test case begins with two integers n and m, denoting numbers of cities and cables, respectively. Then, m lines will follow for specifying the m cables. Each of the m lines contains three positive integers, i, j, and b_i,j, denoting that a cable with a bandwidth of b_i,j directly connects the city pair (i, j), where the cities are numbered from 1 to n, and i < j since b_i,j = b_j,i. No more than one cable will be available between every city pair in the current network. In addition, the bandwidths of all cables are distinct; no two cables have the same bandwidth rating.

The output is a single integer that is the sum of the bandwidths of all city pairs in the optimized network.

• 2 ≤ n ≤ 10000
• 1 ≤ m ≤ 500000
• 1 ≤ i < j ≤ n
• 0 < b_i,j < 10⁷