Dijkstra's Algorithm modified to take negative edge weights
I am afraid your implementation is in \$\Theta(EV)\$ in the worst case, and that is because in the outer while loop you iterate \$V\$ times and popping a node from your custom priority queue runs in \$n = V\$ steps, so we already have \$\Theta(V^2)\$. If your graph is really dense, the complexity will rise to \$\Theta(EV)\$.

In order to get it done efficiently without writing your (say, Fibonacci-) heap, you could import heapq

With it, you can come up with something like:

def sssp(graph, start_node):
    open = [(0, start_node)]
    closed = set()
    distance_map = {start_node: 0}
    while open:
        current_node = heapq.heappop(open)[1]
        if current_node in closed:
            continue
        closed.add(current_node)
        for child, arc_weight in graph[current_node]:
            if child in closed:
                continue
            tentative_distance = distance_map[current_node] + arc_weight
            if child not in distance_map.keys() or distance_map[child] &gt; tentative_distance:
                distance_map[child] = tentative_distance
                heapq.heappush(open, (tentative_distance, child))
    return distance_map


The above runs in \$\Theta((E + V) \log V)\$. Also, the above version has a desirable property: it does not visit nodes that are disconnected from the source node. You might need to know which nodes are not reachable; to this end, you just make a lookup into distance_map: if a node is not there as a key, it is unreachable. This "pruning" may boost the performance if most graph nodes are not reachable from the source node.

About code

Note that PEP8 complains: you should have a single space after , and :. Also, in Python, it is customary to write the class names in CamelCase. Also, in line if  color[j] &lt; temp and color[j] == 'b' you have two spaces after the the if; PEP8 requires one space only.

Hope that helps.

Post scriptum

On G16 = {'a': [('b': -1)], 'b': [('a': -1)]} your implementation goes into an  infinite loop; mine provides invalid results but does exit. If your graph has negative-weight cycles, I suggest you stick to Bellman-Ford; alright, its worst case running time is \$\Theta(EV)\$, but its constant factors are small, since it is just two nested loops.