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]

 
# Scans distances and picks a vertex with min. distance, whose distance has
# not yet been finalized
def getMinDistanceVertex(distances, finalized):
  minDistance = float('Infinity') #Initialize minDistance to a large integer
  
  for v in distances.keys():
    if((not finalized[v]) and (distances[v] < minDistance)):
      minDistance = distances[v]
      minVertex = v

  return minVertex

def min(x, y):
  if(x <= y):
    return x
  else:
    return y
      

# Takes a graph and a source vertex and computes distances of all 
# vertices from the source
def DijkstraShortestPath(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] = 2**20
    tree[v] = v

  distances[source] = 0

  # Initializing the array the indicates whether a vertex's distance-value has been finalized
  finalized = {}
  numFinalized = 0
  for v in g.keys():
    finalized[v] = 0
 
  # Repeatedly process the vertex at the front of the queue
  while(numFinalized < n):
    u = getMinDistanceVertex(distances, finalized)
    finalized[u] = 1
    numFinalized = numFinalized + 1
    nbrs = getNeighbors(g, u)

    # Scan all neighbors of u
    # If a neighbor v has already been finalized, ignore it
    for v in nbrs.keys():
      if(not finalized[v]):
        if(distances[u] + getEdgeWeight(g, u, v) < distances[v]):
          distances[v] = distances[u] + getEdgeWeight(g, u, v)
          tree[v] = u
  
  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])