output_description: Print the sum of the weights of the Minimum Spanning Tree.
input_description: |V| |E|
      s0 t0 w0
      s1 t1 w1
      :
      s|E|-1 t|E|-1 w|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
  wi represents the weight of the i-th edge.
attempt: #!/usr/bin/env python
  # -*- coding: utf-8 -*-
  
  """
  input:
  6 9
  0 1 1
  0 2 3
  1 2 1
  1 3 7
  2 4 1
  1 4 3
  3 4 1
  3 5 1
  4 5 6
  
  output:
  5
  """
  
  import sys
  import heapq as hp
  
  WHITE, GRAY, BLACK = 0, 1, 2
  
  
  def generate_adj_table(v_table):
      for each in v_table:
          v_from, v_to, edge_weight = map(int, each)
          init_adj_table[v_from][v_to] = edge_weight
          init_adj_table[v_to][v_from] = edge_weight
  
      return init_adj_table
  
  
  def prim_span_tree():
      distance[init_v] = 0
      distance_heap = []
      hp.heappush(distance_heap, (0, init_v))
  
      while distance_heap:
          current_vertex = hp.heappop(distance_heap)[1]
  
          color[current_vertex] = BLACK
  
          for adj_vertex, adj_weight in adj_table[current_vertex].items():
              if color[adj_vertex] is not BLACK:
                  if adj_weight < distance[adj_vertex]:
                      distance[adj_vertex] = adj_weight
                      parent[adj_vertex] = current_vertex
                      color[adj_vertex] = GRAY
                      hp.heappush(distance_heap, (adj_weight, adj_vertex))
  
      return distance
  
  
  if __name__ == "__main__":
      _input = sys.stdin.readlines()
      vertices, edges = map(int, _input[0].split())
      v_info = map(lambda x: x.split(), _input[1:])
  
      parent = [-1] * vertices
      distance = [float("inf")] * vertices
      color = [WHITE] * vertices
      init_v = 0
  
      init_adj_table = tuple(dict() for _ in range(vertices))
      adj_table = generate_adj_table(v_info)
      print(sum(prim_span_tree()))
  
problem_description: Minimum Spanning Tree
  
    
  
  Find the sum of weights of edges of the Minimum Spanning Tree for a given
  weighted undirected graph G = (V, E).
samples: [{"input": "4 6\n    0 1 2\n    1 2 1\n    2 3 1\n    3 0 1\n    0 2 3\n    1 3 5", "output": "3"}, {"input": "6 9\n    0 1 1\n    0 2 3\n    1 2 1\n    1 3 7\n    2 4 1\n    1 4 3\n    3 4 1\n    3 5 1\n    4 5 6", "output": "5"}]