Hackerearth - Learning Graph
As for runtime duration, there is not really much you can do, as the algorithm is already optimum.

However, code can be simplified a bit. Here are some tips:


node_value_dict has same data as node_values -> not needed
Use input() instead of sys.stdin.readline().split() so you can avoid an import
Is there a need for connected_graph_component to be a dict? It should be fine as an array of arrays
As for the sorting, note that you can make the key a pair instead of only 1 value and it will sort first by first value, and if equal it sorts according to second value.
list(map(int, sys.stdin.readline().split())) is repeated multiple times, put it in a function
Sometimes batching print calls in 1 call instead of printing for each value is faster


This is my version of the code after applying these tips:

    def read_line_values():
        return list(map(int, input().strip().split(' ')))

    def connect_graph():
        n, m, k = read_line_values()
        node_values = read_line_values()

        connected_graph_component = [[] for _ in range(n + 1)]

        answer = []

        for m_i in range(m):
            n1, n2 = read_line_values()
            connected_graph_component[n1].append(n2)
            connected_graph_component[n2].append(n1)

        for i in range(1, n + 1):

            neighbours = connected_graph_component[i]
            if len(neighbours) &lt; k:
                answer.append("-1")
            else:  
                neighbours.sort(key = lambda node: (node_values[node - 1], node), reverse=True)
                answer.append(str(neighbours[k - 1]))

        print("\n".join(answer))        
    connect_graph()


On a side note, if you run the same code as python 2.7.6 instead of 3.5.2, it´s about 2s faster.