You are a helpful assistant. The assistant first thinks about the reasoning process in the mind and then provides the user with the answer. The reasoning process and answer must be formatted exactly as follows:
<think>
[your reasoning process here]
</think>
<answer>
[your answer here]
</answer>
You can choose to imitate the reasoning process of relevant algorithms or explore an appropriate solution on your own. DO NOT use code, and remember to focus on the logical flow.
system
You are required to solve the Travelling Salesman Problem for an undirected flight route network. Your objective is to determine the shortest possible route that visits each of the listed airports exactly once and returns to the starting point.

**Problem to Solve**

- Airports to visit: PZU, YSM, LUQ, RZR, INL, WLG, VGO, KCZ, PGU
- Travel distances (in kilometers) between each pair of airports:
PZU to VGO: 5124
PZU to LUQ: 12758
PZU to INL: 11704
PZU to WLG: 16037
PZU to PGU: 2151
PZU to RZR: 2421
PZU to YSM: 12302
PZU to KCZ: 9842
YSM to VGO: 8925
YSM to LUQ: 12671
YSM to INL: 2904
YSM to WLG: 13372
YSM to PGU: 12539
YSM to RZR: 11989
YSM to KCZ: 9617
LUQ to VGO: 10938
LUQ to INL: 10789
LUQ to WLG: 12024
LUQ to PGU: 14778
LUQ to RZR: 15048
LUQ to KCZ: 20011
RZR to VGO: 5288
RZR to INL: 11496
RZR to WLG: 15332
RZR to PGU: 1067
RZR to KCZ: 7829
INL to VGO: 8043
INL to WLG: 13842
INL to PGU: 12023
INL to KCZ: 10636
WLG to VGO: 20173
WLG to PGU: 15011
WLG to KCZ: 9990
VGO to PGU: 5815
VGO to KCZ: 11256
KCZ to PGU: 8247
Please calculate the shortest tour and format your answer as follows: [Airport A, Airport B, Airport C, ..., Airport A]
user
{"directed": false, "multigraph": false, "graph": {}, "nodes": [{"name": "PZU", "id": 0}, {"name": "YSM", "id": 1}, {"name": "LUQ", "id": 2}, {"name": "RZR", "id": 3}, {"name": "INL", "id": 4}, {"name": "WLG", "id": 5}, {"name": "VGO", "id": 6}, {"name": "KCZ", "id": 7}, {"name": "PGU", "id": 8}], "links": [{"weight": 5124, "source": 0, "target": 6}, {"weight": 12758, "source": 0, "target": 2}, {"weight": 11704, "source": 0, "target": 4}, {"weight": 16037, "source": 0, "target": 5}, {"weight": 2151, "source": 0, "target": 8}, {"weight": 2421, "source": 0, "target": 3}, {"weight": 12302, "source": 0, "target": 1}, {"weight": 9842, "source": 0, "target": 7}, {"weight": 8925, "source": 1, "target": 6}, {"weight": 12671, "source": 1, "target": 2}, {"weight": 2904, "source": 1, "target": 4}, {"weight": 13372, "source": 1, "target": 5}, {"weight": 12539, "source": 1, "target": 8}, {"weight": 11989, "source": 1, "target": 3}, {"weight": 9617, "source": 1, "target": 7}, {"weight": 10938, "source": 2, "target": 6}, {"weight": 10789, "source": 2, "target": 4}, {"weight": 12024, "source": 2, "target": 5}, {"weight": 14778, "source": 2, "target": 8}, {"weight": 15048, "source": 2, "target": 3}, {"weight": 20011, "source": 2, "target": 7}, {"weight": 5288, "source": 3, "target": 6}, {"weight": 11496, "source": 3, "target": 4}, {"weight": 15332, "source": 3, "target": 5}, {"weight": 1067, "source": 3, "target": 8}, {"weight": 7829, "source": 3, "target": 7}, {"weight": 8043, "source": 4, "target": 6}, {"weight": 13842, "source": 4, "target": 5}, {"weight": 12023, "source": 4, "target": 8}, {"weight": 10636, "source": 4, "target": 7}, {"weight": 20173, "source": 5, "target": 6}, {"weight": 15011, "source": 5, "target": 8}, {"weight": 9990, "source": 5, "target": 7}, {"weight": 5815, "source": 6, "target": 8}, {"weight": 11256, "source": 6, "target": 7}, {"weight": 8247, "source": 7, "target": 8}]}
You are required to solve the Travelling Salesman Problem for an undirected flight route network. Your objective is to determine the shortest possible route that visits each of the listed airports exactly once and returns to the starting point.

**Problem to Solve**

- Airports to visit: PZU, YSM, LUQ, RZR, INL, WLG, VGO, KCZ, PGU
- Travel distances (in kilometers) between each pair of airports:
PZU to VGO: 5124
PZU to LUQ: 12758
PZU to INL: 11704
PZU to WLG: 16037
PZU to PGU: 2151
PZU to RZR: 2421
PZU to YSM: 12302
PZU to KCZ: 9842
YSM to VGO: 8925
YSM to LUQ: 12671
YSM to INL: 2904
YSM to WLG: 13372
YSM to PGU: 12539
YSM to RZR: 11989
YSM to KCZ: 9617
LUQ to VGO: 10938
LUQ to INL: 10789
LUQ to WLG: 12024
LUQ to PGU: 14778
LUQ to RZR: 15048
LUQ to KCZ: 20011
RZR to VGO: 5288
RZR to INL: 11496
RZR to WLG: 15332
RZR to PGU: 1067
RZR to KCZ: 7829
INL to VGO: 8043
INL to WLG: 13842
INL to PGU: 12023
INL to KCZ: 10636
WLG to VGO: 20173
WLG to PGU: 15011
WLG to KCZ: 9990
VGO to PGU: 5815
VGO to KCZ: 11256
KCZ to PGU: 8247
Please calculate the shortest tour and format your answer as follows: [Airport A, Airport B, Airport C, ..., Airport A]
test