There are n cities that want to create a shared train network so that each pair of cities is connected by rail to each of the other cities. The cost of laying track is directly proportional to the distance between two cities. The cost to lay one mile of railroad track is $1M. Your task is to determine the lowest cost possible for laying the track so that all the cities are connected.

Input

A single line containing the number n of cities followed by n city coordinate lines. Each of the coordinate lines is a pair of floating point numbers x y giving the coordinates of the cities on a square grid (for this problem you may assume the earth is flat and that the units of the grid structure are given in miles).

Output

The minimum amount of money (in millions) that must be spent to create the railroad network. You can round this to a single decimal place.

Sample Input	Sample Output
3 0 1.5 1 0 0 0	$2.5M
8 0 0 1 1 0 1 3 3 4 5 2 2 1 0 3 2	$8.7M

Hints

You may use our connected_components.py Download connected_components.py in your code if you want., which will produce labels for each of the vertices that correspond to their component. You will need to use the adjacency list structure as suggested below if you wish to use this code in its unmodified state.
You may have already envisioned a way to represent this problem as a graph. Draw the graph in the small example above on paper. How many edges does it have? If you are unsure of this, check with me before you start coding the solution.

Adjacency List

Augment your dictionary/set based adjacency structure to use a dictionary for the edges (instead of a set as before). This will allow you to store the edge weights as the values of this second dictionary.

Method/Programming requirement

Your program must implement either Borůvka's algorithm (I suggest you use Borůvka's) or Prims (not Kruskal). You must specify which algorithm you are implementing in the comments. Any other method to compute the answer will result in zero credit.

Submission

Submit the code in a file named cs412_railroad_a.py to Gradescope. If you use the supplied copy of connected_components.py, you only need to import it into your code (it will be available on Gradescope, so, no need to submit). If you change connected_components.py, then please rename it and submit it as part of your code (or you can copy/paste the code into your lab and just submit a single file, it is up to you). You can import the code using the following python:

from connected_components import count_and_label