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: TWB, CGI, XNA, CFR, YYU, YIF, QUB, CNM, PKA
- Travel distances (in kilometers) between each pair of airports:
TWB to PKA: 12793
TWB to XNA: 13853
TWB to CGI: 14391
TWB to CFR: 16894
TWB to YYU: 15001
TWB to QUB: 16937
TWB to CNM: 13109
TWB to YIF: 16925
CGI to PKA: 5594
CGI to XNA: 1437
CGI to CFR: 7478
CGI to YYU: 1915
CGI to QUB: 9706
CGI to CNM: 2087
CGI to YIF: 3068
XNA to PKA: 5501
XNA to CFR: 7737
XNA to YYU: 2174
XNA to QUB: 9965
XNA to CNM: 1734
XNA to YIF: 3327
CFR to PKA: 11253
CFR to YYU: 6922
CFR to QUB: 2855
CFR to CNM: 8968
CFR to YIF: 4959
YYU to PKA: 6003
YYU to QUB: 9150
YYU to CNM: 3306
YYU to YIF: 2514
YIF to PKA: 7549
YIF to QUB: 7424
YIF to CNM: 4682
QUB to PKA: 13718
QUB to CNM: 11311
CNM to PKA: 5223
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": "TWB", "id": 0}, {"name": "CGI", "id": 1}, {"name": "XNA", "id": 2}, {"name": "CFR", "id": 3}, {"name": "YYU", "id": 4}, {"name": "YIF", "id": 5}, {"name": "QUB", "id": 6}, {"name": "CNM", "id": 7}, {"name": "PKA", "id": 8}], "links": [{"weight": 12793, "source": 0, "target": 8}, {"weight": 13853, "source": 0, "target": 2}, {"weight": 14391, "source": 0, "target": 1}, {"weight": 16894, "source": 0, "target": 3}, {"weight": 15001, "source": 0, "target": 4}, {"weight": 16937, "source": 0, "target": 6}, {"weight": 13109, "source": 0, "target": 7}, {"weight": 16925, "source": 0, "target": 5}, {"weight": 5594, "source": 1, "target": 8}, {"weight": 1437, "source": 1, "target": 2}, {"weight": 7478, "source": 1, "target": 3}, {"weight": 1915, "source": 1, "target": 4}, {"weight": 9706, "source": 1, "target": 6}, {"weight": 2087, "source": 1, "target": 7}, {"weight": 3068, "source": 1, "target": 5}, {"weight": 5501, "source": 2, "target": 8}, {"weight": 7737, "source": 2, "target": 3}, {"weight": 2174, "source": 2, "target": 4}, {"weight": 9965, "source": 2, "target": 6}, {"weight": 1734, "source": 2, "target": 7}, {"weight": 3327, "source": 2, "target": 5}, {"weight": 11253, "source": 3, "target": 8}, {"weight": 6922, "source": 3, "target": 4}, {"weight": 2855, "source": 3, "target": 6}, {"weight": 8968, "source": 3, "target": 7}, {"weight": 4959, "source": 3, "target": 5}, {"weight": 6003, "source": 4, "target": 8}, {"weight": 9150, "source": 4, "target": 6}, {"weight": 3306, "source": 4, "target": 7}, {"weight": 2514, "source": 4, "target": 5}, {"weight": 7549, "source": 5, "target": 8}, {"weight": 7424, "source": 5, "target": 6}, {"weight": 4682, "source": 5, "target": 7}, {"weight": 13718, "source": 6, "target": 8}, {"weight": 11311, "source": 6, "target": 7}, {"weight": 5223, "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: TWB, CGI, XNA, CFR, YYU, YIF, QUB, CNM, PKA
- Travel distances (in kilometers) between each pair of airports:
TWB to PKA: 12793
TWB to XNA: 13853
TWB to CGI: 14391
TWB to CFR: 16894
TWB to YYU: 15001
TWB to QUB: 16937
TWB to CNM: 13109
TWB to YIF: 16925
CGI to PKA: 5594
CGI to XNA: 1437
CGI to CFR: 7478
CGI to YYU: 1915
CGI to QUB: 9706
CGI to CNM: 2087
CGI to YIF: 3068
XNA to PKA: 5501
XNA to CFR: 7737
XNA to YYU: 2174
XNA to QUB: 9965
XNA to CNM: 1734
XNA to YIF: 3327
CFR to PKA: 11253
CFR to YYU: 6922
CFR to QUB: 2855
CFR to CNM: 8968
CFR to YIF: 4959
YYU to PKA: 6003
YYU to QUB: 9150
YYU to CNM: 3306
YYU to YIF: 2514
YIF to PKA: 7549
YIF to QUB: 7424
YIF to CNM: 4682
QUB to PKA: 13718
QUB to CNM: 11311
CNM to PKA: 5223
Please calculate the shortest tour and format your answer as follows: [Airport A, Airport B, Airport C, ..., Airport A]
test