graph : shortest path2

#!/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())
if t <1 or t>10:
    exit(0)
   
for a0 in xrange(t):
    n,m = raw_input().strip().split(' ')
    n,m = [int(n),int(m)]
   
    if n <2 or n>3000:
        exit(0)
    if m <1 or m>((n*(n-1))/2):
        exit(0)
       
    for a1 in xrange(m):
        x,y,r = raw_input().strip().split(' ')
        x,y,r = [int(x),int(y),float(r)]
       
        if x <1 or x>n:
            exit(0)
       
        if y <1 or y>n:
            exit(0)
       
        if r <1 or r>10**5:
            exit(0)
       
       
       
       
#        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:
            if y in graph[x] and graph[x][y] > r:
                graph[x][y] = r
                if y not in graph.keys():
                    graph[y] = {}
                    graph[y][x] = r
                else:
                    graph[y][x] = r
            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())
    if s <1 or s>n:
        exit(0)
   
    for i in graph.keys():
        if s !=i:
            cost, path = shortestPath(s, i)
            print int(cost),


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