Small-world networks embedded in Euclidean space represent useful cartoon models for a number of real systems such as electronic circuits, communication systems, the large-scale brain architecture and others. Since the small-world behavior relies on the presence of long-range connections that are likely to have a cost which is a growing function of the length, we explore whether it is possible to choose suitable probability distributions for the shortcut lengths so as to preserve the small-world feature and, at the same time, to minimize the network cost. The flow distribution for such networks, and their robustness, are also investigated.