# Code Clash 2019
# Problem 10: Delivery
# https://www.codeclash.org
locations = []
line = input()
while line != "0, 0":
locations.append(
tuple(int(x) for x in line.split(", "))
)
line = input()
starting_location = (0, 0)
def distance(p1, p2):
return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5
def get_permutations(starting_points, next_locations):
permutations = []
if len(next_locations) == 0:
return []
for next_location in next_locations:
new_starting_points = [p for p in starting_points] + [next_location]
permutations.append(new_starting_points)
other_locations = [p for p in next_locations]
other_locations.remove(next_location)
next_permutations = get_permutations(new_starting_points, other_locations)
for p in next_permutations:
permutations.append(p)
return permutations
def get_all_routes():
permutations = get_permutations([(0, 0)], locations)
full_paths = list(filter(lambda p: len(p) == (len(locations) + 1), permutations))
for path in full_paths:
path.append((0, 0))
return full_paths
def get_distance_of_path(path):
if len(path) <= 1: return 0
dist = 0
for i in range(1, len(path)):
dist += distance(path[i - 1], path[i])
return dist
routes = get_all_routes()
min_distance = -1
min_dist_idx = 0
for i in range(len(routes)):
dist = get_distance_of_path(routes[i])
if min_distance == -1 or dist < min_distance:
min_distance = dist
min_dist_idx = i
best_route = routes[min_dist_idx]
if (distance(best_route[0], best_route[1]) > distance(best_route[-1], best_route[2])):
best_route = list(reversed(best_route))
for i in range(1, len(best_route) - 1):
print(str(best_route[i][0]) + ", " + str(best_route[i][1]))