21D - Traveling Graph - CodeForces Solution

INF = 1000 * 1000 * 100

def find_pair_combination(vertexes):
    if not vertexes:
        return 0
    ans = INF
    for i in range(1, len(vertexes)):
        ans = min(ans, dist[vertexes[0]][vertexes[i]] + find_pair_combination(vertexes[1:i] + vertexes[i + 1:]))
    return ans

def build_dijskatra(dist):
  for a in range(n):      for x in range(n):
        for y in range(n):
            dist[x][y] = min(dist[x][y], dist[x][a] + dist[a][y])
  return dist
 
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
_sumEdgeWeight = 0
matr = [[INF] * n for _ in range(n)]
for i in range(m):
    a, b, w = map(int, input().split())
    _sumEdgeWeight += w
    graph[a - 1].append((b - 1, w))
    graph[b - 1].append((a - 1, w))
    matr[a - 1][b - 1] = matr[b - 1][a - 1] = min(matr[a - 1][b - 1], w)
odd = list(a for a in range(n) if len(graph[a]) % 2)
dist = build_dijskatra(matr)
result = find_pair_combination(odd)
if result < INF and max([0] + [dist[0][a] for a in range(1, n) if len(graph[a]) > 0]) < INF:      print(result + _sumEdgeWeight)
else:
    print(-1)