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: WWT, PEK, RNA, LYH, KVG, ZKE, WEI, RAH, SBY
- Travel distances (in kilometers) between each pair of airports:
WWT to PEK: 11795
WWT to LYH: 6605
WWT to SBY: 6578
WWT to KVG: 14620
WWT to RNA: 12679
WWT to WEI: 14831
WWT to RAH: 16108
WWT to ZKE: 6659
PEK to LYH: 11734
PEK to SBY: 11267
PEK to KVG: 7663
PEK to RNA: 8425
PEK to WEI: 8102
PEK to RAH: 7228
PEK to ZKE: 11562
RNA to LYH: 14892
RNA to SBY: 15205
RNA to KVG: 2482
RNA to WEI: 3087
RNA to RAH: 13837
RNA to ZKE: 15257
LYH to SBY: 877
LYH to KVG: 16833
LYH to WEI: 17162
LYH to RAH: 12238
LYH to ZKE: 2230
KVG to SBY: 16964
KVG to WEI: 2325
KVG to RAH: 13075
KVG to ZKE: 16700
ZKE to SBY: 1729
ZKE to WEI: 17267
ZKE to RAH: 11820
WEI to SBY: 17475
WEI to RAH: 12918
RAH to SBY: 11407
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": "WWT", "id": 0}, {"name": "PEK", "id": 1}, {"name": "RNA", "id": 2}, {"name": "LYH", "id": 3}, {"name": "KVG", "id": 4}, {"name": "ZKE", "id": 5}, {"name": "WEI", "id": 6}, {"name": "RAH", "id": 7}, {"name": "SBY", "id": 8}], "links": [{"weight": 11795, "source": 0, "target": 1}, {"weight": 6605, "source": 0, "target": 3}, {"weight": 6578, "source": 0, "target": 8}, {"weight": 14620, "source": 0, "target": 4}, {"weight": 12679, "source": 0, "target": 2}, {"weight": 14831, "source": 0, "target": 6}, {"weight": 16108, "source": 0, "target": 7}, {"weight": 6659, "source": 0, "target": 5}, {"weight": 11734, "source": 1, "target": 3}, {"weight": 11267, "source": 1, "target": 8}, {"weight": 7663, "source": 1, "target": 4}, {"weight": 8425, "source": 1, "target": 2}, {"weight": 8102, "source": 1, "target": 6}, {"weight": 7228, "source": 1, "target": 7}, {"weight": 11562, "source": 1, "target": 5}, {"weight": 14892, "source": 2, "target": 3}, {"weight": 15205, "source": 2, "target": 8}, {"weight": 2482, "source": 2, "target": 4}, {"weight": 3087, "source": 2, "target": 6}, {"weight": 13837, "source": 2, "target": 7}, {"weight": 15257, "source": 2, "target": 5}, {"weight": 877, "source": 3, "target": 8}, {"weight": 16833, "source": 3, "target": 4}, {"weight": 17162, "source": 3, "target": 6}, {"weight": 12238, "source": 3, "target": 7}, {"weight": 2230, "source": 3, "target": 5}, {"weight": 16964, "source": 4, "target": 8}, {"weight": 2325, "source": 4, "target": 6}, {"weight": 13075, "source": 4, "target": 7}, {"weight": 16700, "source": 4, "target": 5}, {"weight": 1729, "source": 5, "target": 8}, {"weight": 17267, "source": 5, "target": 6}, {"weight": 11820, "source": 5, "target": 7}, {"weight": 17475, "source": 6, "target": 8}, {"weight": 12918, "source": 6, "target": 7}, {"weight": 11407, "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: WWT, PEK, RNA, LYH, KVG, ZKE, WEI, RAH, SBY
- Travel distances (in kilometers) between each pair of airports:
WWT to PEK: 11795
WWT to LYH: 6605
WWT to SBY: 6578
WWT to KVG: 14620
WWT to RNA: 12679
WWT to WEI: 14831
WWT to RAH: 16108
WWT to ZKE: 6659
PEK to LYH: 11734
PEK to SBY: 11267
PEK to KVG: 7663
PEK to RNA: 8425
PEK to WEI: 8102
PEK to RAH: 7228
PEK to ZKE: 11562
RNA to LYH: 14892
RNA to SBY: 15205
RNA to KVG: 2482
RNA to WEI: 3087
RNA to RAH: 13837
RNA to ZKE: 15257
LYH to SBY: 877
LYH to KVG: 16833
LYH to WEI: 17162
LYH to RAH: 12238
LYH to ZKE: 2230
KVG to SBY: 16964
KVG to WEI: 2325
KVG to RAH: 13075
KVG to ZKE: 16700
ZKE to SBY: 1729
ZKE to WEI: 17267
ZKE to RAH: 11820
WEI to SBY: 17475
WEI to RAH: 12918
RAH to SBY: 11407
Please calculate the shortest tour and format your answer as follows: [Airport A, Airport B, Airport C, ..., Airport A]
test