def prog_21(fname):

    f = open(fname)
    n = eval(f.readline().strip())

    graphs = {}

    for i in xrange(n):
        nodes,num = map(int, f.readline().strip().split())
        graph = nx.DiGraph()
        fe = None

        for j in xrange(num):
            e1,e2,w = map(int, f.readline().strip().split())
            if j==0:
                fe = (e1,e2)
            graph.add_weighted_edges_from([(e1,e2,w)])

        graphs[i]={'graph':graph, 'edge':fe}

    f.close()

    # print graphs


    for i in xrange(n):
        graph = graphs[i]['graph']
        fe    = graphs[i]['edge']

        try:
            print nx.dijkstra_path_length(graph,fe[0],fe[1])+nx.dijkstra_path_length(graph,fe[1],fe[0]),
        except:
            print -1,

def eight_and_nine(graph, source, target, number):
    if source == target:
        neighbours = graph.successors(source)
        for neighbour in neighbours:
            result = nx.dijkstra_path_length(
                graph, source=source,
                target=neighbour) + nx.dijkstra_path_length(
                graph, source=neighbour, target=target)
    else:
        result = nx.dijkstra_path_length(graph, source=source, target=target)
    return "Output #{}: {}".format(number, result)

def nxShortestPath(nxGraph, nxPos, startPt, endPt, Dijk=0):
    if Dijk == 0:
        nxList = nx.shortest_path(nxGraph, source=startPt, target=endPt)
        score = nx.shortest_path_length(nxGraph, source=startPt, target=endPt)
        dist = nx.shortest_path_length(nxGraph, source=startPt, target=endPt, weight="distance")
    elif Dijk == 1:
        nxList = nx.dijkstra_path(nxGraph, source=startPt, target=endPt, weight="weight")
        score = nx.dijkstra_path_length(nxGraph, source=startPt, target=endPt, weight="weight")
        dist = nx.dijkstra_path_length(nxGraph, source=startPt, target=endPt, weight="distance")

    nxH = nx.subgraph(nxGraph, nxList)
    return nxList, nxH, score, dist

    def test_dijkstra(self):
        (D, P) = nx.single_source_dijkstra(self.XG, 's')
        validate_path(self.XG, 's', 'v', 9, P['v'])
        assert_equal(D['v'], 9)

        validate_path(
            self.XG, 's', 'v', 9, nx.single_source_dijkstra_path(self.XG, 's')['v'])
        assert_equal(dict(
            nx.single_source_dijkstra_path_length(self.XG, 's'))['v'], 9)

        validate_path(
            self.XG, 's', 'v', 9, nx.single_source_dijkstra(self.XG, 's')[1]['v'])
        validate_path(
            self.MXG, 's', 'v', 9, nx.single_source_dijkstra_path(self.MXG, 's')['v'])

        GG = self.XG.to_undirected()
        # make sure we get lower weight
        # to_undirected might choose either edge with weight 2 or weight 3
        GG['u']['x']['weight'] = 2
        (D, P) = nx.single_source_dijkstra(GG, 's')
        validate_path(GG, 's', 'v', 8, P['v'])
        assert_equal(D['v'], 8)     # uses lower weight of 2 on u<->x edge
        validate_path(GG, 's', 'v', 8, nx.dijkstra_path(GG, 's', 'v'))
        assert_equal(nx.dijkstra_path_length(GG, 's', 'v'), 8)

        validate_path(self.XG2, 1, 3, 4, nx.dijkstra_path(self.XG2, 1, 3))
        validate_path(self.XG3, 0, 3, 15, nx.dijkstra_path(self.XG3, 0, 3))
        assert_equal(nx.dijkstra_path_length(self.XG3, 0, 3), 15)
        validate_path(self.XG4, 0, 2, 4, nx.dijkstra_path(self.XG4, 0, 2))
        assert_equal(nx.dijkstra_path_length(self.XG4, 0, 2), 4)
        validate_path(self.MXG4, 0, 2, 4, nx.dijkstra_path(self.MXG4, 0, 2))
        validate_path(
            self.G, 's', 'v', 2, nx.single_source_dijkstra(self.G, 's', 'v')[1]['v'])
        validate_path(
            self.G, 's', 'v', 2, nx.single_source_dijkstra(self.G, 's')[1]['v'])

        validate_path(self.G, 's', 'v', 2, nx.dijkstra_path(self.G, 's', 'v'))
        assert_equal(nx.dijkstra_path_length(self.G, 's', 'v'), 2)

        # NetworkXError: node s not reachable from moon
        assert_raises(nx.NetworkXNoPath, nx.dijkstra_path, self.G, 's', 'moon')
        assert_raises(
            nx.NetworkXNoPath, nx.dijkstra_path_length, self.G, 's', 'moon')

        validate_path(self.cycle, 0, 3, 3, nx.dijkstra_path(self.cycle, 0, 3))
        validate_path(self.cycle, 0, 4, 3, nx.dijkstra_path(self.cycle, 0, 4))

        assert_equal(
            nx.single_source_dijkstra(self.cycle, 0, 0), ({0: 0}, {0: [0]}))

        def connect_virtually(n, m, c):
            # create or reference adjacent nodes
            c_name = '(' + ' '.join(c) + ')'
            try:
                nb = [i for i in self.graph[n]
                      if c_name in i.name and not self.graph.successors(i)][0]
            except IndexError:
                nb = copy.deepcopy(n)
                nb.name = n.name + ' ' + c_name

            try:
                mb = [i for i in self.graph[m]
                      if c_name in i.name and not self.graph.predecessors(i)][0]
            except IndexError:
                mb = copy.deepcopy(m)
                mb.name = m.name + ' ' + c_name

            # connect nodes
            self.graph.add_edge(n, nb, weight=common_intervals[c])
            self.graph.add_edge(nb, n, weight=0.0)

            self.graph.add_edge(m, mb, weight=common_intervals[c])
            self.graph.add_edge(mb, m, weight=0.0)

            tt = nx.dijkstra_path_length(self.graph, n, m)
            self.graph.add_edge(nb, mb, weight=tt)

def cost_split(G,cur,tremdstlist):
 
 csplit=0
 tablesplit=[[]  for i in xrange(len(tremdstlist))]
 num=0
 for j in tremdstlist:
    
     if (cur!=tremdstlist[num]):
           tablesplit[num]=nx.dijkstra_path(G,cur,tremdstlist[num])
     num=num+1
     
 
 csplit=nx.dijkstra_path_length(G,cur,tremdstlist[0])
 #print "CSPLIT added cost from :",cur, "to ",tremdstlist[0],"as ",length[cur][tremdstlist[0]]
 #*print "tablesplit[0]=",tablesplit[0]
 for x in xrange(1,num):
     curpath=tablesplit[x]
     
     for y in xrange(len(curpath)):
         if (y!=len(curpath)-1):
             
             if  ((curpath[y+1] in tablesplit[0]) !=True):
                 curwt=G.edge[curpath[y]][curpath[y+1]]['weight']
                 #print "CSPLIT : Adding [",curpath[y],"][",curpath[y+1],"]"
                 csplit=csplit+curwt
 return csplit

def group_cyclefactor_approx( demand_hist, M, transport_graph, cost_label='cost' ) :
    """ construct and solve the LP relaxation of the IP """
    cost, constr, SERVICE = construct_lp_relaxation( demand_hist, M, transport_graph, cost_label=cost_label )
    prog = cvxpy.program( cvxpy.minimize( cost ), constr )
    res = prog.solve( quiet=DEBUG )
    # still need to debug this garbage!!!! wtf is going on here?
    
    
    """ convert to proper format and "round" the solution """
    fractional = dict()
    
    trips_hist = dict()
    for (i,j) in demand_hist :
        target = dict()
        for edge in itertools.product( M.neighbors_iter(i), M.neighbors_iter(j) ) :
            temp = SERVICE.get_edge_data( *edge ).get('var').value
            fractional[ edge ] = temp
            target[ edge ] = temp
            
        demand_update = greedy_chairman_rounding( target )
        trips_hist.update( demand_update )
        
        
    """ construct and solve the resulting cycle factor instance """
    service_edges = nx.MultiDiGraph()
    for (x,y), NUMTRIPS in trips_hist.iteritems() :
        weight = nx.dijkstra_path_length( transport_graph, x, y, weight=cost_label )
        for k in range(NUMTRIPS) :
            service_edges.add_edge( x,y, cost=weight )
    
    cycles = cyclefactor.cyclefactor( service_edges, transport_graph )
    return cycles

 def weighted_concept_path(self, node1, node2):
     
     '''
     Shortest path between two nodes
     
     :param node1: id of node 1
     :param node2: id of node 2
     :return: shortest path between node1 and node2
     '''
     spath = 0
     
     if self.all_dist:
         try:
             spath = self.all_dist[node1][node2]                
         except:
             raise exception.GraphException((node1, node2), \
                            'No path for this node pair')
     else:
         try:
             spath = nx.dijkstra_path_length(self.G, node1, node2)
         except:
             raise exception.GraphException((node1, node2), \
                            'No path for this node pair')
     
     return spath

    def removeNonConnectedUsers(self, graph, dist_threshold):
        components = nx.connected_components(graph)
        print "Number of connected components: %s" % len(components)

        print "Removing non-connected user nodes"
        remove_nodes = []
        for component in components:
            usernodes = []
            userdists = {}
            for node in component:
                if type(node) == User:
                    usernodes.append(node)
            u1idx = 0
            ulen = len(usernodes)
            for u1 in usernodes:
                u1idx = u1idx + 1
                print "%s/%s" % (u1idx, ulen)
                if not u1.id in userdists:
                    userdists[u1.id] = 1000
                for u2 in usernodes:
                    if u1 == u2:
                        continue
                    pathres = nx.dijkstra_path_length(graph,u1,u2)
                    if pathres < userdists[u1.id]:
                        userdists[pathres] = pathres
                    if userdists[u1.id] < dist_threshold:
                        break # condition satisfied
            for user in usernodes:
                if userdists[user.id] > dist_threshold: # shortest path to another user is > 5 -> remove
                    print "Removing user %s. Dist value: %s" % (user.id, userdists[user.id])
                    remove_nodes.append(user)
        print "Removing %s user nodes" % len(remove_nodes)
        graph.remove_nodes_from(remove_nodes)
        del remove_nodes

    def test_dijkstra(self):
        (D,P)= nx.single_source_dijkstra(self.XG,'s')
        assert_equal(P['v'], ['s', 'x', 'u', 'v'])
        assert_equal(D['v'],9)

        assert_equal(nx.single_source_dijkstra_path(self.XG,'s')['v'],
                     ['s', 'x', 'u', 'v'])
        assert_equal(nx.single_source_dijkstra_path_length(self.XG,'s')['v'],9)

        assert_equal(nx.single_source_dijkstra(self.XG,'s')[1]['v'],
                     ['s', 'x', 'u', 'v'])

        assert_equal(nx.single_source_dijkstra_path(self.MXG,'s')['v'],
                     ['s', 'x', 'u', 'v'])

        GG=self.XG.to_undirected()
        # make sure we get lower weight
        # to_undirected might choose either edge with weight 2 or weight 3
        GG['u']['x']['weight']=2
        (D,P)= nx.single_source_dijkstra(GG,'s')
        assert_equal(P['v'] , ['s', 'x', 'u', 'v'])
        assert_equal(D['v'],8)     # uses lower weight of 2 on u<->x edge
        assert_equal(nx.dijkstra_path(GG,'s','v'), ['s', 'x', 'u', 'v'])
        assert_equal(nx.dijkstra_path_length(GG,'s','v'),8)

        assert_equal(nx.dijkstra_path(self.XG2,1,3), [1, 4, 5, 6, 3])
        assert_equal(nx.dijkstra_path(self.XG3,0,3), [0, 1, 2, 3])
        assert_equal(nx.dijkstra_path_length(self.XG3,0,3),15)
        assert_equal(nx.dijkstra_path(self.XG4,0,2), [0, 1, 2])
        assert_equal(nx.dijkstra_path_length(self.XG4,0,2), 4)
        assert_equal(nx.dijkstra_path(self.MXG4,0,2), [0, 1, 2])
        assert_equal(nx.single_source_dijkstra(self.G,'s','v')[1]['v'],
                     ['s', 'u', 'v'])
        assert_equal(nx.single_source_dijkstra(self.G,'s')[1]['v'],
                     ['s', 'u', 'v'])

        assert_equal(nx.dijkstra_path(self.G,'s','v'), ['s', 'u', 'v'])
        assert_equal(nx.dijkstra_path_length(self.G,'s','v'), 2)

        # NetworkXError: node s not reachable from moon
        assert_raises(nx.NetworkXNoPath,nx.dijkstra_path,self.G,'s','moon')
        assert_raises(nx.NetworkXNoPath,nx.dijkstra_path_length,self.G,'s','moon')

        assert_equal(nx.dijkstra_path(self.cycle,0,3),[0, 1, 2, 3])
        assert_equal(nx.dijkstra_path(self.cycle,0,4), [0, 6, 5, 4])

        assert_equal(nx.single_source_dijkstra(self.cycle,0,0),({0:0}, {0:[0]}) )

def sum_dist_former(key_nodes):
    sum_dist = 0.0
    for node in key_nodes:
        for node_a in key_nodes:
            dis = float(nx.dijkstra_path_length(G, node_a, node))
            sum_dist = sum_dist + dis
    ave_dist = sum_dist/len(key_nodes)
    return ave_dist

def demand_enroute_velocity( lengraph, rategraph, length='length', rate='rate' ) :
    V = 0.
    for u, v, rate_data in rategraph.edges_iter( data=True ) :
        curr_rate = rate_data.get( rate, None )
        if curr_rate is None : continue
        
        dist = nx.dijkstra_path_length( lengraph, u, v, weight=length )
        V += curr_rate * dist
    return V

def nearestPathLen(point1,point2, G):
    try:
        return nx.dijkstra_path_length(G, point1, point2)
    except:
        print 'Illegal Path:',
        print point1,
        print ' ',
        print point2
        return 999999999

    def test_dijkstra(self):
        (D,P)= nx.single_source_dijkstra(self.XG,'s')
        assert_equal(P['v'], ['s', 'x', 'u', 'v'])
        assert_equal(D['v'],9)

        assert_equal(nx.single_source_dijkstra_path(self.XG,'s')['v'], 
                     ['s', 'x', 'u', 'v'])
        assert_equal(nx.single_source_dijkstra_path_length(self.XG,'s')['v'],9)
        
        assert_equal(nx.single_source_dijkstra(self.XG,'s')[1]['v'],
                     ['s', 'x', 'u', 'v'])

        assert_equal(nx.single_source_dijkstra_path(self.MXG,'s')['v'],
                     ['s', 'x', 'u', 'v'])

        GG=self.XG.to_undirected()
        (D,P)= nx.single_source_dijkstra(GG,'s')
        assert_equal(P['v'] , ['s', 'x', 'u', 'v'])
        assert_equal(D['v'],8)     # uses lower weight of 2 on u<->x edge
        assert_equal(nx.dijkstra_path(GG,'s','v'), ['s', 'x', 'u', 'v'])
        assert_equal(nx.dijkstra_path_length(GG,'s','v'),8)

        assert_equal(nx.dijkstra_path(self.XG2,1,3), [1, 4, 5, 6, 3])
        assert_equal(nx.dijkstra_path(self.XG3,0,3), [0, 1, 2, 3])
        assert_equal(nx.dijkstra_path_length(self.XG3,0,3),15)
        assert_equal(nx.dijkstra_path(self.XG4,0,2), [0, 1, 2])
        assert_equal(nx.dijkstra_path_length(self.XG4,0,2), 4)
        assert_equal(nx.dijkstra_path(self.MXG4,0,2), [0, 1, 2])
        assert_equal(nx.single_source_dijkstra(self.G,'s','v')[1]['v'],
                     ['s', 'u', 'v'])
        assert_equal(nx.single_source_dijkstra(self.G,'s')[1]['v'],
                     ['s', 'u', 'v'])

        assert_equal(nx.dijkstra_path(self.G,'s','v'), ['s', 'u', 'v'])
        assert_equal(nx.dijkstra_path_length(self.G,'s','v'), 2)

        # NetworkXError: node s not reachable from moon
        assert_raises(nx.NetworkXNoPath,nx.dijkstra_path,self.G,'s','moon')
        assert_raises(nx.NetworkXNoPath,nx.dijkstra_path_length,self.G,'s','moon')

        assert_equal(nx.dijkstra_path(self.cycle,0,3),[0, 1, 2, 3])
        assert_equal(nx.dijkstra_path(self.cycle,0,4), [0, 6, 5, 4])

        assert_equal(nx.single_source_dijkstra(self.cycle,0,0),(0, [0]) )

def compute_shortest_path(graph, target_node, source_node):
    '''
    Display shortest path result
    '''
    print '\n******* From ' + source_node + ' to ' + target_node + ' *******'
    path = nx.dijkstra_path(graph,source=source_node,target=target_node)
    print 'Path:', path
    path_length = nx.dijkstra_path_length(graph,source=source_node,target=target_node)
    print 'Path weight: ', path_length
    display_path_weights(graph, path)

  def get_shortest_path_through_gateways(self, source):
    "return the path lengths to the source ip address to all the gateways"
    G=nx.DiGraph()
    G.add_weighted_edges_from([(link.lastHopIP, link.destinationIP, link.tcEdgeCost) for link in self.linklist])
    
    paths_length=dict()
    for gw in self.gatewaylist:
      paths_length[gw]=nx.dijkstra_path_length(G, source, gw)

    return paths_length

def dij():
    with open("rosalind_dij.txt") as f:
        n, m = map(int, f.readline().strip().split())
        lines = f.readlines()

    edge_list = map(lambda x: map(int, x.strip().split()), lines)

    # Create the graph
    G = nx.DiGraph()
    G.add_nodes_from(range(1,n+1))
    G.add_weighted_edges_from(edge_list)

    for n in G.nodes():
        try:
            print nx.dijkstra_path_length(G, 1, n),
        except:
            # node is not reachable
            print -1,
    print ""

def StayConnected(N, c):
	G = nx.complete_graph(1)

	for i in range(1, N):
		existingNodes = list(G.nodes())
		random.shuffle(existingNodes)

		optimalToConnect = 0
		optimalUtility = float("-inf")

		for nodeToConnect in existingNodes:
			G.add_edge(i, nodeToConnect)

			sumPathLengths = 0
			for node in G.nodes():
				sumPathLengths -= nx.dijkstra_path_length(G, i, node)

			if sumPathLengths > optimalUtility:
				optimalToConnect = nodeToConnect
				optimalUtility = sumPathLengths

			G.remove_edge(i, nodeToConnect)

		G.add_edge(i,nodeToConnect)

		print optimalUtility

		existingNodes.remove(nodeToConnect)

		for nodeToConnect in existingNodes:
			G.add_edge(i, nodeToConnect)

			sumPathLengths = 0
			for node in G.nodes():
				sumPathLengths -= nx.dijkstra_path_length(G, i, node)

			if sumPathLengths - optimalUtility > c:
				optimalUtility = sumPathLengths
			else:
				G.remove_edge(i, nodeToConnect)

	return G

def main83():
    g = g83(matrix)
    N = len(matrix)
    M = len(matrix[0])
    print "(%d) Nodes, (%d) Edges" % (len(g.nodes()), len(g.edges()))
    start = (0,0)
    end = (N-1, M-1)
    path_d = nx.dijkstra_path(g, start, end)
    print len(path_d), nx.dijkstra_path_length(g, start, end) + g.node[start].get('value')
    for node in path_d:
        print node, g.node[node].get('value'), g[node]

def makecomplete(subset, graph):
    nodes = subset.nodes()
    nodesTwo = subset.nodes()
    result = subset.copy()
    for node in nodes:
	for nodeTwo in nodesTwo:
	    if node != nodeTwo:
	        if not subset.has_edge(node, nodeTwo):
                    shortest_path = nx.dijkstra_path_length(graph,node,nodeTwo)
                    result.add_weighted_edges_from([(node,nodeTwo,shortest_path)])
    return result