output_description: Print the shortest distance in a line.
input_description: |V| |E|
      s0 t0 d0
      s1 t1 d1
      :
      s|E|-1 t|E|-1 d|E|-1
      
  
  , where |V| is the number of vertices and |E| is the number of edges in the
  graph. The graph vertices are named with the numbers 0, 1,..., |V|-1
  respectively.
  
  si and ti represent source and target verticess of i-th edge (undirected) and
  di represents the distance between si and ti (the i-th edge).
  
  Note that there can be multiple edges between a pair of vertices.
attempt: def warshall_floyd(n, links):
      prev = [t.copy() for t in links]
      for i in range(n):
          prev[i][i] = 0
  
      for k in range(n - 1):
          current = [t.copy() for t in prev]
          prev_k = prev[k]
          for i in range(n):
              prev_i, current_i = prev[i], current[i]
              prev_i_k = prev_i[k]
              for j in range(n):
                  current_i[j] = min(prev_i[j], prev_i_k + prev_k[j])
          prev = current
  
      return prev
  
  
  def solve(n, links, total_d, odd_vertices):
      if not odd_vertices:
          return total_d
  
      d_table = warshall_floyd(n, links)
      d_table = [[d for oj, d in enumerate(d_table[oi]) if oj in odd_vertices] for ni, oi in enumerate(odd_vertices)]
      ndt = len(d_table)
      bit_dict = {1 << i: i for i in range(ndt)}
  
      def minimum_pair(remains):
          if not remains:
              return 0
          b = remains & -remains
          remains ^= b
          i = bit_dict[b]
          return min(minimum_pair(remains ^ (1 << j)) + d_table[i][j] for j in range(ndt) if remains & (1 << j))
  
      return total_d + minimum_pair((1 << ndt) - 1)
  
  
  v, e = map(int, input().split())
  
  links = [[float('inf')] * v for _ in range(v)]
  odd_vertices = [0] * v
  total_d = 0
  
  for _ in range(e):
      s, t, d = map(int, input().split())
      links[s][t] = min(links[s][t], d)
      links[t][s] = min(links[t][s], d)
      odd_vertices[s] ^= 1
      odd_vertices[t] ^= 1
      total_d += d
  
  print(solve(v, links, total_d, [i for i, v in enumerate(odd_vertices) if v]))
problem_description: Chinese Postman Problem
  
  For a given weighted undirected graph G(V, E), find the distance of the
  shortest route that meets the following criteria:
  
    * It is a closed cycle where it ends at the same point it starts.
    * The route must go through every edge at least once.
samples: [{"input": "4 4\n    0 1 1\n    0 2 2\n    1 3 3\n    2 3 4", "output": "10"}, {"input": "4 5\n    0 1 1\n    0 2 2\n    1 3 3\n    2 3 4\n    1 2 5", "output": "18"}, {"input": "2 3\n    0 1 1\n    0 1 2\n    0 1 3", "output": "7"}]