Top k closest pairs in a set of million 128-dimensional points
First, cut your work load in half.  You only need to consider pairs where i &lt; j, so:

for i in range(M-1):
    for j in range(i+1, M):
        # ...


If you actually need both (i, j) and (j, i), then you only need the 50 million closest pairs, and can duplicate &amp; swap every pair in the list as the last step.   More savings!

Record &amp; sort the first 100 million (50 million?) pairs.  Then, as new pairs are generated, if closer than the worst stored pair, use bisect.bisect() to find insertion spot, add the new pair, and kick out the worst pair.   

Time: \$O(n^2 log k)\$, 
Space: \$O(k)\$, n is number of points, k is desired number of pairs.