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: MEL, OIM, AKK, WUX, LRH, SYZ, SHD, SAF, CCJ, YPH, ABE, KPV
- Travel distances (in kilometers) between each pair of airports:
MEL to YPH: 16869
MEL to WUX: 8205
MEL to AKK: 13889
MEL to CCJ: 9153
MEL to LRH: 17127
MEL to ABE: 16608
MEL to SAF: 13896
MEL to SYZ: 12194
MEL to KPV: 14152
MEL to OIM: 8573
MEL to SHD: 16541
OIM to YPH: 11315
OIM to WUX: 1942
OIM to AKK: 10670
OIM to CCJ: 7134
OIM to LRH: 10440
OIM to ABE: 11483
OIM to SAF: 9928
OIM to SYZ: 8122
OIM to KPV: 10933
OIM to SHD: 11559
AKK to YPH: 6583
AKK to WUX: 12232
AKK to CCJ: 16978
AKK to LRH: 11134
AKK to ABE: 6111
AKK to SAF: 4892
AKK to SYZ: 15315
AKK to KPV: 1345
AKK to SHD: 6187
WUX to YPH: 12826
WUX to CCJ: 5205
WUX to LRH: 9635
WUX to ABE: 12198
WUX to SAF: 11439
WUX to SYZ: 6749
WUX to KPV: 12495
WUX to SHD: 12273
LRH to YPH: 6889
LRH to CCJ: 8160
LRH to ABE: 6222
LRH to SAF: 8671
LRH to SYZ: 4976
LRH to KPV: 11397
LRH to SHD: 6492
SYZ to YPH: 11136
SYZ to CCJ: 3196
SYZ to ABE: 10779
SYZ to SAF: 12852
SYZ to KPV: 15578
SYZ to SHD: 11049
SHD to YPH: 2415
SHD to CCJ: 13976
SHD to ABE: 450
SHD to SAF: 2912
SHD to KPV: 6450
SAF to YPH: 3549
SAF to CCJ: 15699
SAF to ABE: 2963
SAF to KPV: 5155
CCJ to YPH: 14288
CCJ to ABE: 13705
CCJ to KPV: 17241
YPH to ABE: 2204
YPH to KPV: 6846
ABE to KPV: 6374
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": "MEL", "id": 0}, {"name": "OIM", "id": 1}, {"name": "AKK", "id": 2}, {"name": "WUX", "id": 3}, {"name": "LRH", "id": 4}, {"name": "SYZ", "id": 5}, {"name": "SHD", "id": 6}, {"name": "SAF", "id": 7}, {"name": "CCJ", "id": 8}, {"name": "YPH", "id": 9}, {"name": "ABE", "id": 10}, {"name": "KPV", "id": 11}], "links": [{"weight": 16869, "source": 0, "target": 9}, {"weight": 8205, "source": 0, "target": 3}, {"weight": 13889, "source": 0, "target": 2}, {"weight": 9153, "source": 0, "target": 8}, {"weight": 17127, "source": 0, "target": 4}, {"weight": 16608, "source": 0, "target": 10}, {"weight": 13896, "source": 0, "target": 7}, {"weight": 12194, "source": 0, "target": 5}, {"weight": 14152, "source": 0, "target": 11}, {"weight": 8573, "source": 0, "target": 1}, {"weight": 16541, "source": 0, "target": 6}, {"weight": 11315, "source": 1, "target": 9}, {"weight": 1942, "source": 1, "target": 3}, {"weight": 10670, "source": 1, "target": 2}, {"weight": 7134, "source": 1, "target": 8}, {"weight": 10440, "source": 1, "target": 4}, {"weight": 11483, "source": 1, "target": 10}, {"weight": 9928, "source": 1, "target": 7}, {"weight": 8122, "source": 1, "target": 5}, {"weight": 10933, "source": 1, "target": 11}, {"weight": 11559, "source": 1, "target": 6}, {"weight": 6583, "source": 2, "target": 9}, {"weight": 12232, "source": 2, "target": 3}, {"weight": 16978, "source": 2, "target": 8}, {"weight": 11134, "source": 2, "target": 4}, {"weight": 6111, "source": 2, "target": 10}, {"weight": 4892, "source": 2, "target": 7}, {"weight": 15315, "source": 2, "target": 5}, {"weight": 1345, "source": 2, "target": 11}, {"weight": 6187, "source": 2, "target": 6}, {"weight": 12826, "source": 3, "target": 9}, {"weight": 5205, "source": 3, "target": 8}, {"weight": 9635, "source": 3, "target": 4}, {"weight": 12198, "source": 3, "target": 10}, {"weight": 11439, "source": 3, "target": 7}, {"weight": 6749, "source": 3, "target": 5}, {"weight": 12495, "source": 3, "target": 11}, {"weight": 12273, "source": 3, "target": 6}, {"weight": 6889, "source": 4, "target": 9}, {"weight": 8160, "source": 4, "target": 8}, {"weight": 6222, "source": 4, "target": 10}, {"weight": 8671, "source": 4, "target": 7}, {"weight": 4976, "source": 4, "target": 5}, {"weight": 11397, "source": 4, "target": 11}, {"weight": 6492, "source": 4, "target": 6}, {"weight": 11136, "source": 5, "target": 9}, {"weight": 3196, "source": 5, "target": 8}, {"weight": 10779, "source": 5, "target": 10}, {"weight": 12852, "source": 5, "target": 7}, {"weight": 15578, "source": 5, "target": 11}, {"weight": 11049, "source": 5, "target": 6}, {"weight": 2415, "source": 6, "target": 9}, {"weight": 13976, "source": 6, "target": 8}, {"weight": 450, "source": 6, "target": 10}, {"weight": 2912, "source": 6, "target": 7}, {"weight": 6450, "source": 6, "target": 11}, {"weight": 3549, "source": 7, "target": 9}, {"weight": 15699, "source": 7, "target": 8}, {"weight": 2963, "source": 7, "target": 10}, {"weight": 5155, "source": 7, "target": 11}, {"weight": 14288, "source": 8, "target": 9}, {"weight": 13705, "source": 8, "target": 10}, {"weight": 17241, "source": 8, "target": 11}, {"weight": 2204, "source": 9, "target": 10}, {"weight": 6846, "source": 9, "target": 11}, {"weight": 6374, "source": 10, "target": 11}]}
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: MEL, OIM, AKK, WUX, LRH, SYZ, SHD, SAF, CCJ, YPH, ABE, KPV
- Travel distances (in kilometers) between each pair of airports:
MEL to YPH: 16869
MEL to WUX: 8205
MEL to AKK: 13889
MEL to CCJ: 9153
MEL to LRH: 17127
MEL to ABE: 16608
MEL to SAF: 13896
MEL to SYZ: 12194
MEL to KPV: 14152
MEL to OIM: 8573
MEL to SHD: 16541
OIM to YPH: 11315
OIM to WUX: 1942
OIM to AKK: 10670
OIM to CCJ: 7134
OIM to LRH: 10440
OIM to ABE: 11483
OIM to SAF: 9928
OIM to SYZ: 8122
OIM to KPV: 10933
OIM to SHD: 11559
AKK to YPH: 6583
AKK to WUX: 12232
AKK to CCJ: 16978
AKK to LRH: 11134
AKK to ABE: 6111
AKK to SAF: 4892
AKK to SYZ: 15315
AKK to KPV: 1345
AKK to SHD: 6187
WUX to YPH: 12826
WUX to CCJ: 5205
WUX to LRH: 9635
WUX to ABE: 12198
WUX to SAF: 11439
WUX to SYZ: 6749
WUX to KPV: 12495
WUX to SHD: 12273
LRH to YPH: 6889
LRH to CCJ: 8160
LRH to ABE: 6222
LRH to SAF: 8671
LRH to SYZ: 4976
LRH to KPV: 11397
LRH to SHD: 6492
SYZ to YPH: 11136
SYZ to CCJ: 3196
SYZ to ABE: 10779
SYZ to SAF: 12852
SYZ to KPV: 15578
SYZ to SHD: 11049
SHD to YPH: 2415
SHD to CCJ: 13976
SHD to ABE: 450
SHD to SAF: 2912
SHD to KPV: 6450
SAF to YPH: 3549
SAF to CCJ: 15699
SAF to ABE: 2963
SAF to KPV: 5155
CCJ to YPH: 14288
CCJ to ABE: 13705
CCJ to KPV: 17241
YPH to ABE: 2204
YPH to KPV: 6846
ABE to KPV: 6374
Please calculate the shortest tour and format your answer as follows: [Airport A, Airport B, Airport C, ..., Airport A]
test