Whilst staying in an Aberystwyth holiday home, Santa decides to make some present deliveries to grottos located in a number of towns around Mid Wales.

As Santa needs to have some rest during his pre-Christmas Eve break, he needs to find the route that will minimize the distance he must travel.

The table below gives the distances between each pair of towns, some of which are shown in this diagram:

All distances are in miles.

They represent the direct route 'as the sleigh flies', and are the same in both directions.

Aberystwyth | Builth Wells | Llanidloes | Machynlleth | Newtown | Welshpool | |
---|---|---|---|---|---|---|

Aberystwyth | - | 34 | 23 | 18 | 29 | 43 |

Builth Wells | 34 | - | 27 | 36 | 26 | 37 |

Llanidloes | 23 | 27 | - | 17 | 11 | 22 |

Machynlleth | 18 | 36 | 17 | - | 17 | 30 |

Newtown | 29 | 26 | 11 | 17 | - | 12 |

Welshpool | 43 | 37 | 22 | 30 | 12 | - |

Find the route that starts and ends in Aberystwyth and minimizes the distance that Santa must travel to deliver presents to all towns.

Merry Christmas!