Since the maximum possible number of pairings is $$$10395$$$, I could just check all possible pairings for a cycle. But I'm not sure how I would implement this.

I have no clue. I do not think a brute force would work here.

I can precalculate shortest paths between the pharmacies, fixing the starting and ending. Then for every other vertex, I could take the minimum over all choices of starting and ending pharmacies. Then I could take the overall minimum. It works, but I'm having trouble implementing so much neatly.