假设确定每条边是否经过，只需要满足起点终点的度数为奇数，其余点度数为偶数，并且图连通即可。初始时图的每个点度数都是偶数，所以我们需要删掉一条起点到终点的路径，并且保持图连通。

因为图的每个三角形满足三角形不等式，所以最短路最多经过每个三角形的一条边，从而每个三角形至少剩两条边，所以一定连通。因此只需要求最短路，删掉最短路上的边之后求欧拉路径即可。

时间复杂度 $O(n^2\log n)$。