New advances in gravitational waves observations
The Advanced Laser Interferometer Gravitational-Wave Observatory Two (ALIGO II) is undergoing
a major overhaul. A calibration network connecting all wave detectors has to be built.
Each connection between a pair of detectors is a costly item and therefore the network
topology should not contain any cycles.
The cost of each connection is proportional to its length. The positions of all detectors are fixed.
Thus, the cost of each possible connection between a pair of detectors is known in advance.
If the length was the only ruling parameter then the obvious choice would be to build the network
in the form of a minimum spanning tree of the graph which reflects all possible connections and their lengths.
However, as one might expect, there are other issues to be taken into account in the project of this size.
Theoretical calculations have indicated that the reliability of the system
increases dramatically when some connections in the network share the same length.
In fact, it has been shown that the noise interference in this specific kind of network falls
off exponentially with the number of connections of the same length.
Considering the theory, the technical advisory board of the observatory has decided that the
network building strategy should include three basic rules:
- The network has to be a tree.
- The network should contain maximum possible number of connections of some particular length, regardless of the cost associated with those connections.
- The total length of a network respecting the first and the second rule should be minimized.
Image 1. Schemes of possible connections between pairs of detectors. The detectors are depicted as nodes, the possible connections are depicted as edges. The connections which may form the desired network are highlighted in red. The cases a), b), c) correspond to the Examples 1, 2, 3 below. Note that in some cases (e.g. in cases b and c) more than one network may satisfy the problem demands. However, all such networks share the same total length. Also note that the case a) illustrates the importance of rule 3. There exist spanning trees containing edges (1, 5) and (5, 4) which satisfy rule 2 but do not satisfy rule 3 as the total length of any of them is at least 17. |
The task
You are given a list of all possible connections between the detectors and the respective connection lengths. Calculate the total length of a network which satisfies all three rules presented by the technical advisory board.
Input
The first line of the input consists of two integers N and M separated by space. Value N is the number of detectors. Value M is the number of possible connections between pairs of detectors. Next, there are M lines, where each line represents one possible connection. The line contains three integers D_{1}, D_{2}, L separated by space, meaning that the length of possible connection between detectors D_{1} and D_{2} is equal to L. The detectors are numbered from 1 to N. The possible connections are listed in a random order. It holds N ≤ 30000 and M ≤ 300000. Each length is at most 10^{9}.
Output
The output is one line containing the minimum total length of the required network. The result is not greater than 2^{60}.
Example 1
Input5 6 1 2 6 2 3 6 5 3 1 5 4 5 1 5 5 4 1 2Output
15Example 1 input data and the resulting network are depicted in Image 1 a).
Example 2
Input5 9 1 2 1 2 4 3 4 3 2 3 1 2 1 4 2 3 5 2 1 5 1 2 5 1 4 5 3Output
7Example 2 input data and the resulting network are depicted in Image 1 b).
Example 3
Input9 20 1 2 5 2 3 1 3 4 2 4 5 2 5 6 1 6 7 7 7 8 6 8 1 6 9 1 5 9 2 7 9 3 3 9 4 5 9 5 4 9 6 7 9 7 4 9 8 3 7 1 4 1 3 6 3 5 2 5 7 3Output
19Example 3 input data and the resulting network are depicted in Image 1 c).
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set