graph shortest path

#!/bin/python
import heapq

graph = {}

def shortestPath(start, end):
    queue,seen = [(0, start, [])], set()
    while True:
            (cost, v, path) = heapq.heappop(queue)
            if v not in seen:
                path = path + [v]
                seen.add(v)
                if v == end:
                    return cost, path
            for (next, c) in graph[v].iteritems():
                heapq.heappush(queue, (cost + c, next, path))

t = int(raw_input().strip())
for a0 in xrange(t):
    n,m = raw_input().strip().split(' ')
    n,m = [int(n),int(m)]
    for a1 in xrange(m):
        x,y,r = raw_input().strip().split(' ')
        x,y,r = [int(x),int(y),int(r)]
#        print x,y,r
        if x not in graph.keys():
            graph[x] = {}
            graph[x][y] = r
            if y not in graph.keys():
                graph[y] = {}
                graph[y][x] = r
            else:
                graph[y][x] = r
#            print "if"
#            print graph
        else:
            graph[x][y] = r
            if y not in graph.keys():
                graph[y] = {}
                graph[y][x] = r
            else:
                graph[y][x] = r
#            print "else"
#            print graph

    s = int(raw_input().strip())
    print graph
    print s
    cost, path = shortestPath(s, 3)
    print cost, path


               
#cost, path = shortestPath( x, y)
#print cost, path