def buildGraph(fileref):
  # Read and parse the first line of input.
  # This contains the the number of vertices and the number of edges
  line = fileref.readline()
  graphSize = line.split()
  n = int(graphSize[0])      # n is the number of vertices
  m = int(graphSize[1])      # m is the number of edges

  # The graph will be stored as a dictionary whose keys are the vertices
  # This loop processes the lines corresponding to vertex names
  graph = {}
  for i in range(0, n):
    line = fileref.readline()
    vertex = line.split()
    # The neighbors of each vertex are also stored in a dictionary and this is
    # being initialized below
    graph[vertex[0]] = {}
    
  # The lines in the input file corresponding to edges are processsed
  for i in range(0, m):
    edge = fileref.readline()
    endpoints = edge.split()
    graph[endpoints[0]][endpoints[1]] = int(endpoints[2])
    graph[endpoints[1]][endpoints[0]] = int(endpoints[2])

  return graph

# Takes a graph and a source vertex and computes distances of all 
# vertices from the source
def breadthFirstSearch(g, source):
  n = len(g)
  
  # Initializes the distances of all vertices from the source to n.
  # Note that n is larger than the largest valid distance.
  # Also initializes the shortest path tree
  distances = {}
  tree = {}
  for v in g.keys():
    distances[v] = n
    tree[v] = v

  # Initializing the queue
  queue = [source]
  distances[source] = 0

  # Repeatedly process the vertex at the front of the queue
  while(len(queue) > 0):
    u = queue.pop(0)
    nbrs = getNeighbors(g, u)

    # Scan all neighbors of u, the vertex at the front of the queue
    # If a neighbor v has already been visited, ignore it
    for v in nbrs.keys():
      if(distances[v] == n):
        distances[v] = distances[u] + 1
        tree[v] = u
        queue.append(v)
  
  return [distances, tree]

  

def getNeighbors(graph, v):
  return graph[v]

def isEdge(graph, u, v):
  return (u in graph[v].keys())

def getEdgeWeight(graph, u, v):
  return graph[u][v]

def main():

  fileref = open(pickAFile(), 'r')
  graph = buildGraph(fileref)

  for v in graph.keys():
    printNow(v)
    printNow(graph[v])