*Get a matrix with the values;
*Sum the numbers of the matrix lines, generating one sum per line (The line has the distance from one city to others);
*Find the cities that have the 3 biggest sums and connect the cities with it other (E.g. A-B-C-A);
*The previous step will generate rows (E.g. AB; AC; BC);
*For every next city (that will be the biggest remaining sum, coming from the sums made in the second step):
-for all the already generated rows:
--sum the distance from the actual city to both of the row cities and subtract the row size (Generating a cost).
-get the row with the smallest cost delete this row and add 2 new ones, from the actual city to the cities that were forming the deleted row.
*Just do the steps from the NP-hard version and at the end sum the the path to see if it is smaller than the given number.