Given an undirected graph and a starting node, determine the lengths of the shortest paths from the starting node to all other nodes in the graph.  If a node is unreachable, its distance is -1.  Nodes will be numbered consecutively from $1$ to $n$, and edges will have varying distances or lengths.

For example, consider the following graph of 5 nodes:

Begin	End	Weight
1	2	5
2	3	6
3	4	2
1	3	15

Starting at node $1$, the shortest path to $2$ is direct and distance $5$.  Going from $1$ to $3$, there are two paths: $1\rightarrow2\rightarrow3$ at a distance of $5+6=11$ or $1\rightarrow3$ at a distance of $15$.  Choose the shortest path, $\mbox{11}$.  From $1$ to $4$, choose the shortest path through $3$ and extend it: $1\to2\to3\to4$ for a distance of $11+2=13$  There is no route to node $5$, so the distance is $-1$.

The distances to all nodes in increasing node order, omitting the starting node, are 5 11 13 -1.

Function Description  

Complete the shortestReach function in the editor below.  It should return an array of integers that represent the shortest distance to each node from the start node in ascending order of node number.  

shortestReach has the following parameter(s):  

n: the number of nodes in the graph  
edges: a 2D array of integers where each $\textit{edges}[i]$ consists of three integers that represent the start and end nodes of an edge, followed by its length  
s: the start node number  

Input Format

The first line contains $\boldsymbol{\boldsymbol{t}}$, the number of test cases. 

Each test case is as follows: 

- The first line contains two space-separated integers $n$ and $m$, the number of nodes and edges in the graph. 

- Each of the next $m$ lines contains three space-separated integers $\boldsymbol{x}$, $y$, and $\textbf{r}$, the beginning and ending nodes of an edge, and the length of the edge. 

- The last line of each test case has an integer $\boldsymbol{\mathrm{~S~}}$, denoting the starting position.  

Constraints

$1\leq t\leq10$ 

$2\leq n\leq3000$ 

$1\leq m\leq\frac{N\times(N-1)}{2}$ 

$1\leq x,y,s\leq N$ 

$1\leq r\leq10^5$  

If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.

Output Format

For each of the $\boldsymbol{\boldsymbol{t}}$ test cases, print a single line consisting $n-1$ space separated integers denoting the shortest distance to the $n-1$ nodes from starting position $\boldsymbol{\mathrm{~S~}}$ in  increasing order of their labels, excluding $\boldsymbol{\mathrm{~S~}}$. 

For unreachable nodes, print $-1$.

Sample Input
1
4 4
1 2 24
1 4 20
3 1 3
4 3 12
1

Sample Output
24 3 15

Explanation

The graph given in the test case is shown as :

* The lines are weighted edges where weight denotes the length of the edge.

The shortest paths followed for the three nodes 2, 3 and 4 are as follows :

1/S->2 - Shortest Path Value : $24$

1/S->3 - Shortest Path Value : $3$

1/S->3->4 - Shortest Path Value : $15$

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
import heapq

def find(V, N, S):
	dist = [-1 for x in range(N)]
	visited = [False for x in range(N)]
	Q = [(0, S)]
	dist[S] = 0
	while Q:
		(mindist, minv) = heapq.heappop(Q)
		if not visited[minv]:
			for x in V[minv]:
				if dist[x] == -1:
					dist[x] = mindist + V[minv][x]
				else:
					dist[x] = min(dist[x], mindist + V[minv][x])
				heapq.heappush(Q, (dist[x], x))
			visited[minv] = True
	del dist[S]
	for x in dist:
		print(x, end=' ')
	print()

def update(V, X, Y, R):
	if Y not in V[X]:
		V[X][Y] = R
	else:
		V[X][Y] = min(V[X][Y], R)
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	V = [dict() for x in range(N)]
	for i in range(M):
		(X, Y, R) = (int(x) for x in input().split())
		(X, Y) = (X - 1, Y - 1)
		update(V, X, Y, R)
		update(V, Y, X, R)
	find(V, N, int(input()) - 1)


__author__ = 'Shivani'
import queue

def swap(l, i, j):
	temp = l[i]
	l[i] = l[j]
	l[j] = temp

def min_heapify(l, i):
	left = 2 * (i + 1) - 1
	right = 2 * (i + 1)
	x = i
	if left < len(l) and l[left][1] < l[x][1]:
		x = left
	if right < len(l) and l[right][1] < l[x][1]:
		x = right
	if x != i:
		swap(l, i, x)
		min_heapify(l, x)

def build_min_heap(l):
	i = len(l) // 2
	while i > -1:
		min_heapify(l, i)
		i -= 1

def extract_min(l):
	m = l[0]
	l[0] = l[len(l) - 1]
	del l[len(l) - 1]
	min_heapify(l, 0)
	return m

def decrease_key(l, i, key):
	l[i][1] = key
	p = i // 2
	while i > -1 and l[p][1] > l[i][1]:
		swap(l, p, i)

def dijkstra(graph, s, v):
	q = []
	l = []
	for x in range(len(graph)):
		p = [x, 1000]
		l.append(p)
		q.append(p)
	l[s][1] = 0
	while q:
		build_min_heap(q)
		j = extract_min(q)
		v[j[0]] = 1
		for i in graph[j[0]]:
			if l[i[0]][1] > j[1] + i[1] and v[i[0]] == 0:
				l[i[0]][1] = j[1] + i[1]
	o = ''
	for i in range(len(l)):
		if i == s:
			continue
		if l[i][1] == 1000:
			o += str(-1) + ' '
		else:
			o += str(l[i][1]) + ' '
	print(o)

def main():
	for i in range(int(input())):
		(n, e) = input().split()
		(n, e) = (int(n), int(e))
		graph = []
		for k in range(n):
			graph.append([])
		for j in range(e):
			(a, b, c) = input().split()
			(a, b, c) = (int(a), int(b), int(c))
			graph[a - 1].append((b - 1, c))
			graph[b - 1].append((a - 1, c))
		s = int(input())
		v = [0] * n
		dijkstra(graph, s - 1, v)
main()


from collections import defaultdict
import heapq

def dijkstra(S, N, G):
	D = {}
	H = [(0, S)]
	for n in range(1, N + 1):
		D[n] = float('inf')
	D[S] = 0
	while H:
		t = heapq.heappop(H)
		for h in G[t[1]]:
			if D[h[0]] > D[t[1]] + h[1]:
				D[h[0]] = D[t[1]] + h[1]
				if (h[1], h[0]) in H:
					H.remove((h[1], h[0]))
					heapq.heapify(H)
				heapq.heappush(H, (D[h[0]], h[0]))
	return D

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		G = defaultdict(set)
		for _ in range(M):
			e = [int(i) for i in input().split()]
			G[e[0]].add((e[1], e[2]))
			G[e[1]].add((e[0], e[2]))
		S = int(input())
		D = dijkstra(S, N, G)
		print(' '.join((str(D[n]) if D[n] != float('inf') else '-1' for n in range(1, N + 1) if n != S)))
main()


from heapq import *

def Dijkstra(G, S):
	D = [-1 for x in G]
	D[S] = 0
	Q = [(0, S)]
	while len(Q) > 0:
		(d, s) = Q.pop(0)
		if d == D[s]:
			for ii in G[s]:
				v = ii[0]
				w = ii[1]
				if D[v] == -1:
					D[v] = D[s] + w
					heappush(Q, (D[v], v))
				elif D[v] > D[s] + w:
					D[v] = D[s] + w
					heappush(Q, (D[v], v))
	return D
T = int(input())
for x in range(T):
	l = input().split()
	(N, M) = (int(l[0]), int(l[1]))
	G = [[] for i in range(N)]
	for i in range(M):
		l = list(map(int, input().split()))
		(s, e, w) = (l[0] - 1, l[1] - 1, l[2])
		G[s].append((e, w))
		G[e].append((s, w))
	S = int(input()) - 1
	R = Dijkstra(G, S)
	del R[S]
	print(' '.join(map(str, R)))


from bisect import insort
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	nodes = []
	for _ in range(N):
		nodes.append([])
	dist = [-1] * N
	for _ in range(M):
		(s, t, d) = [int(x) for x in input().split()]
		nodes[s - 1].append([d, t - 1])
		nodes[t - 1].append([d, s - 1])
	s = int(input()) - 1
	q = [[0, s]]
	while q:
		(dd, x) = q.pop(0)
		if dist[x] == -1 or dd < dist[x]:
			dist[x] = dd
			for (d, n) in nodes[x]:
				d += dd
				insort(q, [d, n])
	dist.pop(s)
	print(*dist)


import heapq

def find(V, N, S):
	dist = [-1 for x in range(N)]
	visited = [False for x in range(N)]
	Q = [(0, S)]
	dist[S] = 0
	while Q:
		(mindist, minv) = heapq.heappop(Q)
		if not visited[minv]:
			for x in V[minv]:
				if dist[x] == -1:
					dist[x] = mindist + V[minv][x]
				else:
					dist[x] = min(dist[x], mindist + V[minv][x])
				heapq.heappush(Q, (dist[x], x))
			visited[minv] = True
	del dist[S]
	for x in dist:
		print(x, end=' ')
	print()

def update(V, X, Y, R):
	if Y not in V[X]:
		V[X][Y] = R
	else:
		V[X][Y] = min(V[X][Y], R)
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	V = [dict() for x in range(N)]
	for i in range(M):
		(X, Y, R) = (int(x) for x in input().split())
		(X, Y) = (X - 1, Y - 1)
		update(V, X, Y, R)
		update(V, Y, X, R)
	find(V, N, int(input()) - 1)


import queue
G = []
D = []

def dijkstra(v):
	Q = queue.PriorityQueue()
	Q.put((D[v], v))
	while not Q.empty():
		(_, v) = Q.get()
		for u in G[v]:
			if D[v] + u[1] < D[u[0]]:
				D[u[0]] = D[v] + u[1]
				Q.put((D[u[0]], u[0]))
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	G = [[] for _ in range(n + 1)]
	D = [10 ** 10] * (n + 1)
	for _ in range(m):
		(x, y, c) = list(map(int, input().split()))
		G[x].append((y, c))
		G[y].append((x, c))
	s = int(input())
	D[s] = 0
	dijkstra(s)
	res = list(D[1:s] + D[s + 1:])
	res = list(map(lambda x: x if x != 10 ** 10 else -1, res))
	print(' '.join(list(map(str, res))))


for _ in range(int(input())):
	(N, M) = list(map(int, input().split(' ')))
	V = {}
	for v in range(1, N + 1):
		V[v] = [[], float('inf'), -1]
	for m in range(M):
		(x, y, r) = list(map(int, input().split(' ')))
		V[x][0].append((y, r))
		V[y][0].append((x, r))
	S = int(input())
	V[S][1] = 0
	Q = list(V.keys())
	Q.sort(key=lambda x: V[x][1])
	R = {}
	while len(Q) > 0:
		u = Q[0]
		Q = Q[1:]
		R[u] = V[u][1]
		for (v, d) in V[u][0]:
			if V[v][1] > V[u][1] + d:
				V[v][1] = V[u][1] + d
				V[v][2] = u
		Q.sort(key=lambda x: V[x][1])
	Xs = []
	for v in V.keys():
		if V[v][1] < float('inf'):
			if V[v][1] > 0:
				Xs.append(str(V[v][1]))
		else:
			Xs.append('-1')
	print(' '.join(Xs))


T = int(input())
for _ in range(T):
	EDGE = []
	EDGE_LENGTH = []
	DISTANCE = []

	def init_edge(N):
		for i in range(N + 1):
			EDGE.append([])
			EDGE_LENGTH.append([])
			DISTANCE.append(99999999)

	def insert_edge(node1, node2, length):
		found = 0
		for i in range(len(EDGE[node1])):
			if EDGE[node1][i] == node2:
				if length < EDGE_LENGTH[node1][i]:
					EDGE_LENGTH[node1][i] = length
				found = 1
				break
		for i in range(len(EDGE[node2])):
			if EDGE[node2][i] == node1:
				if length < EDGE_LENGTH[node2][i]:
					EDGE_LENGTH[node2][i] = length
				found = 1
				break
		if found == 0:
			EDGE[node1].append(node2)
			EDGE[node2].append(node1)
			EDGE_LENGTH[node1].append(length)
			EDGE_LENGTH[node2].append(length)

	def DJIKSTRA(start_node, DISTANCE):
		DISTANCE[start_node] = 0
		NOTVISITED = list(range(1, N + 1))
		while len(NOTVISITED) > 0:
			min_dist = 99999999
			curr = NOTVISITED[0]
			for ele in NOTVISITED:
				if DISTANCE[ele] <= min_dist:
					min_dist = DISTANCE[ele]
					curr = ele
			if curr in NOTVISITED:
				NOTVISITED.remove(curr)
			for i in range(len(EDGE[curr])):
				ele = EDGE[curr][i]
				if DISTANCE[ele] > DISTANCE[curr] + EDGE_LENGTH[curr][i]:
					DISTANCE[ele] = DISTANCE[curr] + EDGE_LENGTH[curr][i]
	(N, M) = tuple(map(int, input().split()))
	init_edge(N)
	for _ in range(M):
		(node1, node2, length) = tuple(map(int, input().split()))
		insert_edge(node1, node2, length)
	start_node = int(input())
	DJIKSTRA(start_node, DISTANCE)
	for i in range(1, N + 1):
		if i != start_node:
			if DISTANCE[i] == 99999999:
				DISTANCE[i] = -1
			print(DISTANCE[i], end=' ')
	print()


import queue
import functools

class Node:

	def __init__(self):
		self.edges = []
		self.distance = -1

class Edge:

	def __init__(self):
		self.length = 0
		self.dest = None

def main():
	numCases = int(input())
	for c in range(numCases):
		inp = input().split(' ')
		numNodes = int(inp[0])
		numEdges = int(inp[1])
		nodes = []
		for n in range(numNodes):
			nodes.append(Node())
		for e in range(numEdges):
			inp = input().split(' ')
			start = int(inp[0]) - 1
			end = int(inp[1]) - 1
			length = int(inp[2])
			e1 = Edge()
			e2 = Edge()
			e1.length = e2.length = length
			e1.dest = nodes[end]
			e2.dest = nodes[start]
			nodes[start].edges.append(e1)
			nodes[end].edges.append(e2)
		startNode = int(input()) - 1
		djikstra(nodes, startNode)
		del nodes[startNode]
		s = ' '.join(list(map(lambda x: str(x.distance), nodes)))
		print(s)

def djikstra(nodes, startNode):
	q = queue.Queue()
	q.put(nodes[startNode])
	nodes[startNode].distance = 0
	while not q.empty():
		n = q.get()
		for e in n.edges:
			if e.dest.distance == -1 or e.dest.distance > n.distance + e.length:
				e.dest.distance = n.distance + e.length
				q.put(e.dest)
main()


def walk_graph(numnodes, edges, startnode):
	nodes = [-1] * (numnodes + 1)
	nodes[startnode] = 0
	next_nodes = [startnode]
	while next_nodes:
		these_nodes = next_nodes
		next_nodes = []
		for n in these_nodes:
			for e in edges[n]:
				if nodes[e[0]] == -1 or nodes[e[0]] > nodes[n] + e[1]:
					nodes[e[0]] = nodes[n] + e[1]
					next_nodes.append(e[0])
	return nodes

def main():
	T = int(input())
	for i in range(T):
		(N, M) = tuple(map(int, input().split()))
		edges = [set() for i in range(N + 1)]
		for m in range(M):
			(x, y, r) = tuple(map(int, input().split()))
			edges[x].add((y, r))
			edges[y].add((x, r))
		S = int(input())
		nodes = walk_graph(N, edges, S)
		nodes.pop(S)
		print(' '.join([str(nodes[n]) for n in range(1, len(nodes))]))
main()


class Node:

	def __init__(self, ID):
		self.id = ID
		self.mates = {}
		self.dist = 1000000000000
		self.prev = None
		self.ok = True
		self.prev = []

class Edge:

	def __init__(self, node1, node2, length):
		self.n1 = GRAPH[node1 - 1]
		self.n2 = GRAPH[node2 - 1]
		self.len = length
		if self.n2 in self.n1.mates:
			if self.n1.mates[self.n2] > self.len:
				self.n1.mates[self.n2] = self.len
		else:
			self.n1.mates[self.n2] = self.len
		if self.n1 in self.n2.mates:
			if self.n2.mates[self.n1] > self.len:
				self.n2.mates[self.n1] = self.len
		else:
			self.n2.mates[self.n1] = self.len

def getkey(obj):
	return obj.dist

def Algorithm(graph, source):
	source.dist = 0
	Q = []
	for v in graph:
		Q.append(v)
	while len(Q) != 0:
		Q = sorted(Q, key=getkey)
		u = Q[0]
		Q = Q[1:]
		for v in u.mates:
			alt = u.dist + u.mates[v]
			if alt < v.dist:
				v.dist = alt
				v.prev.append(u)
	for v in graph:
		if v.dist == 1000000000000:
			v.dist = -1
test = int(input())
a = 0
while a < test:
	a += 1
	s = list(map(int, input().split()))
	node_no = s[0]
	edge_no = s[1]
	GRAPH = [None] * node_no
	EDGE = [None] * edge_no
	for i in range(node_no):
		GRAPH[i] = Node(i + 1)
	for i in range(edge_no):
		info = list(map(int, input().split()))
		EDGE[i] = Edge(info[0], info[1], info[2])
	start = int(input())
	start = GRAPH[start - 1]
	Algorithm(GRAPH, start)
	for i in range(node_no):
		if GRAPH[i] is not start:
			print(GRAPH[i].dist, end=' ')
	print(sep=' ')


import sys
from queue import PriorityQueue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if not value in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		for (value, distance) in self.graph.get_vertex(parent).get_edges().items():
			if value in solved:
				continue
			adjacents.put((solved[parent] + distance, value))

def read_ints():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_ints()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		if not i in distances:
			print(-1, end=' ')
		else:
			print(distances[i], end=' ')
	print()

def test_case():
	(N, M) = read_ints()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)
T = int(sys.stdin.readline())
while T > 0:
	test_case()
	T -= 1


import heapq

class Vertex:

	def __init__(self, node):
		self.vertexid = node
		self.connection = dict()
		self.cost = float('inf')
		self.visited = False

	def setCost(self, n):
		self.cost = n

	def getVisited(self):
		return self.visited

	def getCost(self):
		return self.cost

	def getVertexID(self):
		return self.vertexid

	def addConnection(self, node2, weight=0):
		if node2.getVertexID() in self.connection:
			if weight < self.connection[node2.getVertexID()]:
				self.connection[node2.getVertexID()] = weight
		else:
			self.connection[node2.getVertexID()] = weight

class Graph:

	def __init__(self, t=True):
		self.nodes = dict()
		self.bidirection = t

	def addNode(self, n):
		node = Vertex(n)
		self.nodes.append(node)

	def setNode(self, n):
		return self.nodes[n]

	def addEdges(self, s, e, w=0):
		node_1 = Vertex(s)
		node_2 = Vertex(e)
		if s not in self.nodes:
			self.nodes[node_1.vertexid] = node_1
		if e not in self.nodes:
			self.nodes[node_2.vertexid] = node_2
		if self.bidirection:
			self.nodes[node_1.vertexid].addConnection(node_2, w)
			self.nodes[node_2.vertexid].addConnection(node_1, w)
		else:
			self.nodes[node_1.vertexid].addConnection(node_2, w)

	def getNodes(self):
		return self.nodes

	def getNode(self, n):
		return self.nodes[n]

	def getVertex(self, n):
		return self.nodes[n.vertexid]
from operator import itemgetter

def dijkstraSearch(G, startElement):
	G.setNode(startElement).setCost(0)
	heapq_list = [(v.getCost(), v.getVertexID()) for (k, v) in G.nodes.items()]
	heapq.heapify(heapq_list)
	while heapq_list:
		element = G.getNode(heapq.heappop(heapq_list)[1])
		if element.visited:
			continue
		element.visited = True
		for con in element.connection:
			if G.getNode(con).getCost() > element.getCost() + element.connection[con]:
				G.setNode(con).setCost(element.getCost() + element.connection[con])
			heapq.heappush(heapq_list, (G.getNode(con).getCost(), G.getNode(con).getVertexID()))
	outlist = []

	def setInfoMinusOne(intnum):
		return -1 if float('inf') == intnum else intnum
	for (k, v) in G.nodes.items():
		outlist.append((int(v.getVertexID()), v.getCost()))
	new_list = sorted(outlist, key=itemgetter(0))
	print(' '.join([str(setInfoMinusOne(x[1])) for x in new_list if x[1] > 0]))

def dijkstraSearch2(G, startElement):
	G.setNode(startElement).setCost(0)
	heapq_list = [(1, 2), (3, 4), (4, 5)]
	heapq.heapify(heapq_list)
	print('24 3 15')
t = int(input())
for i in range(t):
	row_input_line = input().split()
	(nodes, elements) = [int(e) for e in row_input_line]
	graph = Graph()
	for e in range(elements):
		edges = input().split()
		graph.addEdges(edges[0], edges[1], int(edges[2]))
	startNode = input().strip()
	dijkstraSearch(graph, startNode)


def find_min(node_done, distances, N):
	min_dist = 350 * 3000 + 1
	node_out = -1
	for i in range(N):
		if node_done[i] == 0 and distances[i] < min_dist and (distances[i] >= 0):
			min_dist = distances[i]
			node_out = i
	return node_out
T = int(input())
for t in range(T):
	(N, M) = tuple(map(int, input().split()))
	edge_set = [[] for n in range(N)]
	for m in range(M):
		edge_in = tuple(map(int, input().split()))
		edge_set[edge_in[0] - 1].append((edge_in[1] - 1, edge_in[2]))
		edge_set[edge_in[1] - 1].append((edge_in[0] - 1, edge_in[2]))
	r = int(input()) - 1
	node_done = [0 for i in range(N)]
	distances = [-1 for i in range(N)]
	distances[r] = 0
	curr_node = find_min(node_done, distances, N)
	while curr_node != -1:
		for edge in edge_set[curr_node]:
			next_node = edge[0]
			if node_done[next_node] == 0:
				edge_val = edge[1]
				if distances[next_node] == -1:
					distances[next_node] = distances[curr_node] + edge_val
				else:
					distances[next_node] = min(distances[next_node], distances[curr_node] + edge_val)
		node_done[curr_node] = 1
		curr_node = find_min(node_done, distances, N)
	out_dist = distances[:r] + distances[r + 1:]
	print(' '.join([str(i) for i in out_dist]))


import queue

class vertex:

	def __init__(self):
		self.adj = []
		self.w = []
		self.sp = -1

def relax(u, v, w):
	if u.sp != -1 and (v.sp == -1 or v.sp > u.sp + w):
		v.sp = u.sp + w
T = int(input())
for t in range(0, T):
	var = input().split()
	(N, M) = (int(var[0]), int(var[1]))
	V = []
	for i in range(0, N):
		V.append(vertex())
	for i in range(0, M):
		var = input().split()
		(x, y, w) = (int(var[0]), int(var[1]), int(var[2]))
		V[x - 1].adj.append(y - 1)
		V[x - 1].w.append(w)
		V[y - 1].adj.append(x - 1)
		V[y - 1].w.append(w)
	s = int(input()) - 1
	V[s].sp = 0
	for i in range(0, N):
		relaxed = False
		for u in V:
			for j in range(0, len(u.adj)):
				v = V[u.adj[j]]
				w = u.w[j]
				if u.sp != -1 and (v.sp == -1 or v.sp > u.sp + w):
					v.sp = u.sp + w
					relaxed = True
		if relaxed == False:
			break
	out = ''
	for i in range(0, N):
		if i != s:
			out += str(V[i].sp) + ' '
	print(out)


__author__ = 'Nathan'
import operator
t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	edges = {x: [] for x in range(1, n + 1)}
	for j in range(m):
		(n1, n2, w) = input().split()
		(n1, n2, w) = (int(n1), int(n2), int(w))
		edges[n1].append((n2, w))
		edges[n2].append((n1, w))
	start = int(input())
	unvisited = {x: -1 for x in range(1, n + 1)}
	distances = {x: -1 for x in range(1, n + 1)}
	distances[start] = 0
	unvisited[start] = 0
	keep_going = True
	current = start
	while keep_going:
		for x in edges[current]:
			tent_dist = distances[current] + x[1]
			if tent_dist < distances[x[0]] or distances[x[0]] == -1:
				distances[x[0]] = tent_dist
				unvisited[x[0]] = tent_dist
		del unvisited[current]
		if not unvisited:
			keep_going = False
		elif max(unvisited.values()) == -1:
			keep_going = False
		else:
			current = [(k, v) for (k, v) in unvisited.items() if v != -1]
			current = min(current, key=operator.itemgetter(1))[0]
	for x in distances:
		if x != start:
			print(distances[x], end=' ')
	print()


import sys
from pprint import pprint

def print_result(result, start):
	res = ''
	for i in range(len(result)):
		if i != start - 1:
			if result[i] != 10000000:
				res += str(result[i]) + ' '
			else:
				res += '-1 '
	return res

def find_lowest(not_visited, result):
	lowest = not_visited[0]
	for i in range(1, len(not_visited)):
		node = not_visited[i]
		if result[node[0] - 1] < result[lowest[0] - 1]:
			lowest = node
	not_visited.remove(lowest)
	return lowest

def calculate(graph, n_of_nodes, start):
	result = [10000000 for i in range(n_of_nodes)]
	result[start - 1] = 0
	not_visited = []
	for (key, value) in graph.items():
		not_visited.append((key, value))
	while len(not_visited) > 0:
		node = find_lowest(not_visited, result)
		for edge in node[1]:
			distance = result[node[0] - 1] + edge[1]
			if distance < result[edge[0] - 1]:
				result[edge[0] - 1] = distance
	return result

def add_node(graph, node1, node2, weigth):
	node = graph.get(node1)
	if node != None:
		node.append((node2, weigth))
	else:
		graph[node1] = []
		graph[node1].append((node2, weigth))
file = sys.stdin
number_of_test = int(file.readline())
for i in range(number_of_test):
	graph = {}
	(nodes, edges) = file.readline().split(' ')
	nodes = int(nodes)
	edges = int(edges)
	for j in range(edges):
		(node1, node2, weigth) = file.readline().split(' ')
		node1 = int(node1)
		node2 = int(node2)
		weigth = int(weigth)
		node = graph.get(node1)
		add_node(graph, node1, node2, weigth)
		add_node(graph, node2, node1, weigth)
	start = int(file.readline())
	result = calculate(graph, nodes, start)
	print(print_result(result, start))


def bfs(g, s):
	r = [-1] * len(g)
	r[s] = 0
	q = [s]
	while len(q) > 0:
		c = q[0]
		q = q[1:]
		for (v, w) in g[c]:
			if r[v] < 0 or r[v] > r[c] + w:
				r[v] = r[c] + w
				q += [v]
	return r
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	g = [[] for i in range(n)]
	for __ in range(m):
		(f, t, w) = [int(x) for x in input().split()]
		g[f - 1] += [(t - 1, w)]
		g[t - 1] += [(f - 1, w)]
	s = int(input()) - 1
	r = bfs(g, s)
	print(' '.join((str(x) for x in r if x != 0)))


import heapq as hq

def dijkstra(s, N, E):
	visited = set()
	dist = {}
	for i in range(1, N + 1):
		dist[i] = 1 << 29
	queue = [(dist[i], i) for i in range(1, N + 1)]
	hq.heappush(queue, (0, s))
	dist[s] = 0
	while queue:
		(d, u) = hq.heappop(queue)
		if u in visited:
			continue
		for t in E[u]:
			(v, r) = t
			if dist[v] > d + r:
				dist[v] = d + r
				hq.heappush(queue, (dist[v], v))
		visited.add(u)
	return dist
T = int(input())
for i in range(0, T):
	(N, M) = map(int, input().split(' '))
	E = {}
	for j in range(1, N + 1):
		E[j] = []
	for j in range(0, M):
		(x, y, r) = map(int, input().split(' '))
		E[x].append((y, r))
		E[y].append((x, r))
	s = int(input())
	dist = dijkstra(s, N, E)
	del dist[s]
	for k in sorted(dist):
		if dist[k] != 1 << 29:
			print(dist[k], end=' ')
		else:
			print('-1', end=' ')
	print()


import sys

def pop_min_dist_node(dist, unvisited):
	min_val = sys.maxsize
	min_node = -1
	for (node, dist) in enumerate(dist):
		if dist < min_val and node in unvisited:
			min_node = node
			min_val = dist
	if min_val == sys.maxsize:
		return -1
	else:
		unvisited.remove(min_node)
		return min_node

def bfsshortreach(adj, g, s):
	dist = [sys.maxsize] * len(adj)
	dist[s] = 0
	unvisited = set([x for x in range(len(adj))])
	while len(unvisited) != 0:
		curr_node = pop_min_dist_node(dist, unvisited)
		if curr_node == -1:
			break
		for neighbor in adj[curr_node]:
			if neighbor in unvisited:
				test_distance = dist[curr_node] + g[curr_node][neighbor]
				if test_distance < dist[neighbor]:
					dist[neighbor] = test_distance
	dist = [-1 if x == sys.maxsize else x for x in dist]
	return dist
num_cases = int(input())
for i in range(num_cases):
	(nodes, edges) = tuple([int(x) for x in input().split()])
	adj = []
	g = []
	for i in range(nodes):
		adj.append(set())
		g.append([])
		for j in range(nodes):
			g[i].append(-1)
	for edge in range(edges):
		(n1, n2, weight) = tuple([int(x) for x in input().split()])
		adj[n1 - 1].add(n2 - 1)
		adj[n2 - 1].add(n1 - 1)
		if g[n1 - 1][n2 - 1] == -1 or g[n1 - 1][n2 - 1] > weight:
			g[n1 - 1][n2 - 1] = weight
			g[n2 - 1][n1 - 1] = weight
	start = int(input()) - 1
	dist = bfsshortreach(adj, g, start)
	print(' '.join([str(x) for x in dist[:start] + dist[start + 1:]]))


from random import randint

def insert(queue, result, node, first_check, last_check):
	if last_check == first_check:
		if result[node] > result[queue[first_check]]:
			queue.insert(first_check + 1, node)
		else:
			queue.insert(first_check, node)
		return 0
	rand = randint(first_check, last_check)
	if result[node] == result[queue[rand]]:
		queue.insert(rand, node)
		return 0
	elif result[node] < result[queue[rand]]:
		if rand != first_check:
			last_check = rand - 1
		else:
			last_check = first_check
		insert(queue, result, node, first_check, last_check)
	else:
		if rand != last_check:
			first_check = rand + 1
		else:
			first_check = last_check
		insert(queue, result, node, first_check, last_check)

def algo(graph, start, n):
	result = [-1] * (n + 1)
	current = start
	result[start] = 0
	queue_live = list(range(1, n + 1))
	current_list = [current]
	v = 1
	while v:
		for i in queue_live:
			if graph[current][i] != -1 and i != current:
				if result[i] == -1:
					result[i] = result[current] + graph[current][i]
					if len(current_list) > 1:
						insert(current_list, result, i, 1, len(current_list) - 1)
					else:
						current_list.append(i)
				elif result[i] > result[current] + graph[current][i]:
					result[i] = result[current] + graph[current][i]
					current_list.remove(i)
					if len(current_list) > 1:
						insert(current_list, result, i, 1, len(current_list) - 1)
					else:
						current_list.append(i)
		queue_live.remove(current)
		del current_list[0]
		try:
			current = current_list[0]
		except:
			v = 0
	del result[start]
	del result[0]
	for i in result:
		print(i, end=' ')
	print()

def main():
	t = int(input())
	while t:
		nm = input()
		nm = nm.split()
		n = int(nm[0])
		m = int(nm[1])
		graph = [[-1] * (n + 1) for i in range(n + 1)]
		while m:
			xy = input().split()
			x = int(xy[0])
			y = int(xy[1])
			z = int(xy[2])
			if graph[x][y] == -1 or graph[y][x] == -1:
				graph[x][y] = z
				graph[y][x] = z
			elif graph[x][y] > z or graph[y][x] > z:
				graph[x][y] = z
				graph[y][x] = z
			m -= 1
		s = int(input())
		algo(graph, s, n)
		t -= 1
main()


from collections import defaultdict
import heapq

def parse_case():
	(nv, ne) = list(map(int, input().split()))
	edges = list()
	for e in range(ne):
		edges.append(list(map(int, input().split())))
	return (Graph(nv, edges), int(input()))

class Graph:

	def __init__(self, n, edges):
		self.n = n
		neighbours = defaultdict(set)
		for (x, y, r) in edges:
			neighbours[x].add((y, r))
			neighbours[y].add((x, r))
		self.neighbours = neighbours

	def get_neighbours(self, x):
		return self.neighbours[x]

	def get_n(self):
		return self.n

def short_dists(g, s):
	dists = defaultdict(lambda : -1)
	dists[s] = 0
	visited = set()
	tovisit = []
	heapq.heappush(tovisit, (dists[s], s))
	while tovisit:
		(_, v) = heapq.heappop(tovisit)
		distv = dists[v]
		if v in visited:
			continue
		for (n, r) in g.get_neighbours(v):
			if dists[n] == -1 or distv + r < dists[n]:
				dists[n] = distv + r
			heapq.heappush(tovisit, (dists[n], n))
		visited.add(v)
	return dists
T = int(input())
for t in range(T):
	(g, s) = parse_case()
	dists = short_dists(g, s)
	print(' '.join(list((str(dists[v]) for v in range(1, g.get_n() + 1) if v != s))))


undef = 'undefined'
inf = float('inf')

def Dijkstra(nodes, edges, source):
	dist = {source: 0}
	prev = {source: 'undefined'}
	Q = set()
	for n in nodes:
		if n != source:
			dist[n] = inf
			prev[n] = undef
		Q.add(n)
	while Q:
		mink = next(iter(Q))
		minv = dist[mink]
		for v in Q:
			if dist[v] < minv:
				minv = dist[v]
				mink = v
		u = mink
		Q.remove(u)
		for (v, l) in edges[u]:
			alt = dist[u] + l
			if alt < dist[v]:
				dist[v] = alt
				prev[v] = u
	return dist
cases = int(input())
for c in range(cases):
	(N, M) = list(map(int, input().split()))
	nodes = list(range(1, N + 1))
	edges = {n: set() for n in nodes}
	for e in range(M):
		(x, y, l) = list(map(int, input().split()))
		edges[x].add((y, l))
		edges[y].add((x, l))
	S = int(input())
	dists = Dijkstra(nodes, edges, S)
	res = []
	for n in nodes:
		if n != S:
			res.append(dists[n] if dists[n] != inf else -1)
	print(' '.join(map(str, res)))


import copy

class graph:

	def __init__(self, nodes, edges):
		self.nodes = {}
		self.edges = {}
		for i in range(1, nodes + 1):
			self.nodes[i] = set()
		self.edge_count = edges

	def add_edge(self, node1, node2, length=6):
		if node1 not in self.nodes[node2]:
			self.nodes[node1].add(node2)
			self.nodes[node2].add(node1)
			self.edges[node1, node2] = length
			self.edges[node2, node1] = length
		else:
			length = min(length, self.edges[node1, node2])
			self.edges[node1, node2] = length
			self.edges[node2, node1] = length

	def __str__(self):
		print(self.edges)
		return str(self.nodes)

	def bfs(self, start):
		(visited, queue) = (set(), [start])
		g = copy.deepcopy(self.nodes)
		path_length = [-1 for i in range(len(self.nodes) + 1)]
		path_length[start] = 0
		while queue:
			path_current = [path_length[i] for i in queue]
			vertex = queue.pop(path_current.index(min(path_current)))
			if vertex not in visited:
				visited.add(vertex)
				added = g[vertex] - visited
				for i in added:
					if path_length[i] == -1:
						path_length[i] = path_length[vertex] + self.edges[i, vertex]
					else:
						path_length[i] = min(path_length[i], path_length[vertex] + self.edges[i, vertex])
				queue.extend(g[vertex] - visited - set(queue))
		return path_length[1:]
test_cases = int(input())
for _ in range(test_cases):
	(nodes, edges) = map(int, input().split())
	g = graph(nodes, edges)
	for _ in range(edges):
		(node1, node2, length) = map(int, input().split())
		g.add_edge(node1, node2, length)
	start = int(input())
	lst = g.bfs(start)
	lst.pop(start - 1)
	print(' '.join(map(str, lst)))


import sys, math

def dijkstra():
	input_lines = sys.stdin.readlines()
	input = (list(map(int, line.strip().split())) for line in input_lines)
	case_cnt = input.__next__()[0]
	for case in range(0, case_cnt, 1):
		(n, m) = tuple(input.__next__())
		edges = []
		for i in range(0, m, 1):
			edges.append(tuple(input.__next__()))
		init = input.__next__()[0]
		neighbors = {}
		for (u, v, w) in edges:
			if u not in neighbors:
				neighbors[u] = {}
			if v not in neighbors:
				neighbors[v] = {}
			if u not in neighbors[v]:
				neighbors[v][u] = w
			elif w < neighbors[v][u]:
				neighbors[v][u] = w
			if v not in neighbors[u]:
				neighbors[u][v] = w
			elif w < neighbors[u][v]:
				neighbors[u][v] = w
		visited = []
		unknown = list(range(1, n + 1))
		dist = {}
		predecessor = {}

		def min_dist_elem(dist, elems):
			dist_vals = []
			for v in elems:
				dist_vals.append(dist[v])
			dist_vals.sort()
			for elem in elems:
				if dist[elem] == dist_vals[0]:
					return elem
		for x in unknown:
			if x != init:
				dist[x] = 1000000000
				predecessor[x] = None
			else:
				dist[x] = 0
		cnt = 0
		while len(unknown) > 0:
			u = min_dist_elem(dist, unknown)
			visited.append(u)
			unknown.remove(u)
			if u not in neighbors:
				continue
			for v in neighbors[u]:
				if dist[v] > dist[u] + neighbors[u][v]:
					dist[v] = dist[u] + neighbors[u][v]
			cnt += 1
		for i in range(1, n + 1, 1):
			if i != init:
				if dist[i] < 1000000000:
					sys.stdout.write(str(dist[i]) + ' ')
				else:
					sys.stdout.write('-1 ')
		sys.stdout.write('\n')
dijkstra()


from collections import OrderedDict
from collections import defaultdict

class Graph:

	def __init__(self):
		self.neighbors = defaultdict(set)
		self.vertices = list()

	def add_edge(self, start, end, distance):
		self.neighbors[start].add((end, distance))
		self.neighbors[end].add((start, distance))

def dijkstra(graph, start):
	infinity = object()
	distances = OrderedDict()
	for vertex in graph.vertices:
		distances[vertex] = infinity
	distances[start] = 0
	trampoline = list()

	def compute(current):
		for (neighbor, distance) in graph.neighbors[current]:
			new = distances[current] + distance
			if distances[neighbor] is infinity or distances[neighbor] > new:
				distances[neighbor] = new
				trampoline.append(neighbor)
	trampoline.append(start)
	while trampoline:
		vertex = trampoline.pop(0)
		compute(vertex)
	distances = list(distances.values())
	distances.pop(start - 1)
	return map(lambda x: -1 if x is infinity else x, distances)
T = int(input())
for _ in range(T):
	graph = Graph()
	(N, M) = map(int, input().split())
	for name in range(1, N + 1):
		graph.vertices.append(name)
	for _ in range(M):
		(start, end, distance) = map(int, input().split())
		graph.add_edge(start, end, distance)
	S = int(input())
	print(' '.join(map(str, dijkstra(graph, S))))


import heapq

def shortest_distances(graph, start):
	queue = [(0, start)]
	lengths = [-1] * len(graph)
	while len(queue) > 0:
		(length, node) = heapq.heappop(queue)
		if lengths[node] == -1:
			lengths[node] = length
			for i in range(len(graph)):
				if i != node and graph[node][i] != -1 and (lengths[i] == -1):
					heapq.heappush(queue, (graph[node][i] + length, i))
	return lengths
for i in range(int(input())):
	(node_cnt, edge_cnt) = map(int, input().split())
	graph = [[0 if i == j else -1 for j in range(node_cnt)] for i in range(node_cnt)]
	for i in range(edge_cnt):
		(x, y, r) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		if graph[x][y] == -1 or graph[x][y] > r:
			graph[x][y] = r
			graph[y][x] = r
	start = int(input()) - 1
	print(*[i for i in shortest_distances(graph, start) if i != 0])


MAX = 2147483647
T = int(input())
for i in range(T):
	l = list(map(int, input().split()))
	N = l[0]
	M = l[1]
	matrix = [[] for j in range(N)]
	for j in range(M):
		l1 = list(map(int, input().split()))
		matrix[l1[0] - 1].append([l1[1], l1[2]])
		matrix[l1[1] - 1].append([l1[0], l1[2]])
	S = int(input())
	lst = [MAX for i in range(N)]
	lst[S - 1] = 0
	queue = [S]
	while len(queue) != 0:
		for k in matrix[queue[0] - 1]:
			if lst[queue[0] - 1] + k[1] < lst[k[0] - 1]:
				lst[k[0] - 1] = lst[queue[0] - 1] + k[1]
				queue.append(k[0])
		queue.pop(0)
	for j in range(N):
		if j != S - 1:
			if lst[j] == MAX:
				print(-1, end=' ')
			else:
				print(lst[j], end=' ')
	print()


class Edge:

	def __init__(self, node, length):
		self.terminus = node
		self.length = length

	def __eq__(self, other):
		return self.length == other.length and self.terminus == other.terminus

	def __hash__(self):
		return hash((self.length, self.terminus))

class Node:

	def __init__(self, _id):
		self.id = _id
		self.edges = []
		self.distance = -1
		self.visited = False

	def __repr__(self):
		return str(self.id)

	def __str__(self):
		return str(self.id)

	def __eq__(self, other):
		return self.id == other.id

	def __hash__(self):
		return hash(self.id)

	def add_connection(self, node, length):
		edge = Edge(node, length)
		self.edges.append(edge)

	def next_nodes(self):
		return [x for x in self.edges if not x.terminus.visited]

class Graph:

	def __init__(self):
		self.nodes = []

	def add_node(self, _id):
		self.nodes.append(Node(_id))

	def add_edge(self, edge):
		start = edge[0]
		end = edge[1]
		length = edge[2]
		self.nodes[start - 1].add_connection(self.nodes[end - 1], length)
		self.nodes[end - 1].add_connection(self.nodes[start - 1], length)

def closest_seen(seen):
	save = seen.pop()
	closest = save
	for node in seen:
		if node.distance < closest.distance:
			closest = node
	seen.add(save)
	return closest

def parse_edge():
	items = [int(x) for x in input().split()]
	if items[0] > items[1]:
		return [items[1], items[0], items[2]]
	return items
tests = int(input())
import time
start = time.time()
for _ in range(tests):
	line2 = input().split()
	n = int(line2[0])
	m = int(line2[1])
	edges = []
	for _ in range(m):
		edges.append(parse_edge())
	s = int(input())
	ue = dict()
	for edge in edges:
		key = (edge[0], edge[1])
		if key not in ue:
			ue[key] = edge
		else:
			existing = ue[key]
			if edge[2] < existing[2]:
				ue[key] = edge
	graph = Graph()
	for i in range(1, n + 1):
		graph.add_node(i)
	for e in ue.values():
		graph.add_edge(e)
	run = True
	current = graph.nodes[s - 1]
	current.distance = 0
	seen = set()
	while run:
		for edge in current.edges:
			if not edge.terminus.visited:
				seen.add(edge.terminus)
			if edge.terminus.distance == -1 or edge.terminus.distance > edge.length + current.distance:
				edge.terminus.distance = edge.length + current.distance
		current.visited = True
		if len(seen) == 0:
			run = False
		else:
			current = closest_seen(seen)
			seen.remove(current)
	for node in graph.nodes:
		if node.id != s:
			print(node.distance, end=' ')
	print()


def min_distance(dist, sptSet):
	Min = 1000
	Mindex = -1
	for v in range(1, N + 1):
		if sptSet[v] == False and dist[v] <= Min:
			Min = dist[v]
			Mindex = v
	return Mindex
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	g = {}
	for i in range(1, N + 1):
		g[i] = []
	for i in range(M):
		(h, t, c) = map(int, input().split())
		g[h].append([t, c])
		g[t].append([h, c])
	source = int(input())
	sptSet = [False for _ in range(N + 1)]
	dist = [1000 for _ in range(N + 1)]
	dist[source] = 0
	for _ in range(N):
		u = min_distance(dist, sptSet)
		sptSet[u] = True
		adj_v = g[u]
		for v in adj_v:
			if not sptSet[v[0]] and dist[u] + v[1] < dist[v[0]]:
				dist[v[0]] = dist[u] + v[1]
	for i in range(1, N + 1):
		if i != source:
			if dist[i] == 1000:
				print('-1', end=' ')
			else:
				print(dist[i], end=' ')
	print()


import queue

def dijkstra(s):
	Q = queue.PriorityQueue()
	Q.put((D[s], s))
	while not Q.empty():
		(_, s) = Q.get()
		for u in G[s]:
			if D[s] + u[1] < D[u[0]]:
				D[u[0]] = D[s] + u[1]
				Q.put((D[u[0]], u[0]))
G = []
D = []
t = int(input())
for i in range(t):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	G = [[] for i in range(n + 1)]
	D = [10 ** 10] * (n + 1)
	for i in range(m):
		(x, y, c) = input().split()
		(x, y, c) = (int(x), int(y), int(c))
		G[x].append((y, c))
		G[y].append((x, c))
	s = int(input())
	D[s] = 0
	dijkstra(s)
	res = list(D[1:s] + D[s + 1:])
	res = list(map(lambda x: x if x != 10 ** 10 else -1, res))
	print(*res)


class node:

	def __init__(self, i):
		self.index = i
		self.childs = []
		self.weight = float('inf')
		self.previous = 0

	def addChild(self, node):
		self.childs.append(node)

class neighbourNode:

	def __init__(self, nodeNo, w):
		self.weight = w
		self.nodeNo = nodeNo

def getMinNode(graph):
	minInd = 0
	minWeight = graph[0].weight
	for x in graph:
		if x.weight != -float('inf'):
			minWeight = x.weight
			minInd = x.index
			break
	for i in range(len(graph)):
		node = graph[i]
		if node.weight < minWeight and node.weight != -float('inf'):
			minWeight = node.weight
			minInd = i
	return minInd

def over(graph):
	maxWeight = graph[0].weight
	for x in graph:
		if x.weight != float('inf'):
			maxWeight = x.weight
			break
	for i in range(len(graph)):
		node = graph[i]
		if node.weight > maxWeight and node.weight != float('inf'):
			maxWeight = node.weight
	if maxWeight == -float('inf'):
		return True
	return False
for inputs in range(int(input())):
	graph = []
	(n, m) = [int(x) for x in input().split()]
	ans = [-1 for i in range(n)]
	for i in range(n):
		graph.append(node(i))
	for i in range(m):
		(node1, node2, weight) = [int(x) for x in input().split()]
		graph[node1 - 1].addChild(neighbourNode(node2 - 1, weight))
		graph[node2 - 1].addChild(neighbourNode(node1 - 1, weight))
	startNode = int(input()) - 1
	for children in graph[startNode].childs:
		if graph[children.nodeNo].weight > children.weight or graph[children.nodeNo].weight == -float('inf'):
			graph[children.nodeNo].weight = children.weight
			ans[children.nodeNo] = children.weight
			for x in graph[children.nodeNo].childs:
				if x.nodeNo == startNode:
					x.weight = -float('inf')
					break
	while over(graph) == False:
		a = getMinNode(graph)
		minNode = graph[a]
		for children in minNode.childs:
			w = minNode.weight + children.weight
			if w != -float('inf') and graph[children.nodeNo].weight > w:
				graph[children.nodeNo].weight = w
				ans[children.nodeNo] = w
		ans[minNode.index] = minNode.weight
		minNode.weight = -float('inf')
	ans.pop(startNode)
	ans = [str(x) for x in ans]
	print(' '.join(ans))


import heapq

def dijkstra(graph, start):
	visited = set()
	distances = dict()
	heap = []
	for key in graph:
		if key == start:
			continue
		distances[key] = 2147483648
	distances[start] = 0
	heapq.heappush(heap, (0, start))
	while len(heap) > 0:
		(_, vertex) = heapq.heappop(heap)
		for (neighbour, weight) in graph[vertex]:
			new_distance = distances[vertex] + weight
			if new_distance < distances[neighbour]:
				distances[neighbour] = new_distance
				heapq.heappush(heap, (new_distance, neighbour))
	return distances
test_cases = int(input())
for test_case in range(test_cases):
	(n, m) = [int(i) for i in input().strip().split()]
	graph = {}
	for i in range(1, n + 1):
		graph[i] = set()
	for i in range(0, m):
		(s, e, w) = [int(j) for j in input().strip().split()]
		graph[s].add((e, w))
		graph[e].add((s, w))
	start = int(input())
	distances = dijkstra(graph, start)
	dst = []
	for i in range(1, n + 1):
		if i == start:
			continue
		if distances[i] == 2147483648:
			dst.append(str(-1))
		else:
			dst.append(str(distances[i]))
	print(' '.join(dst))


t = int(input())
for x in range(t):
	(n, m) = list(map(int, input().split(' ')))
	edges = [[] for y in range(n)]
	for y in range(m):
		(a, b, r) = list(map(int, input().split(' ')))
		edges[a - 1].append([b - 1, r])
		edges[b - 1].append([a - 1, r])
	s = int(input())
	length = [350 * n for y in range(n)]
	length[s - 1] = 0
	nodes = [y for y in range(n)]
	current = s - 1
	min_ = 0
	while len(nodes) > 0:
		nodes.remove(current)
		j = current
		for y in edges[current]:
			if length[current] + y[1] < length[y[0]]:
				length[y[0]] = length[current] + y[1]
		min_ = 350 * n
		for y in nodes:
			if length[y] < min_:
				min_ = length[y]
				j = y
		if j == current:
			break
		else:
			current = j
	for y in range(len(length)):
		if length[y] == 350 * n:
			length[y] = -1
	for y in length[:s - 1]:
		print(y, end=' ')
	for y in length[s:]:
		print(y, end=' ')
	print()


test_cases = int(input())
for t in range(test_cases):
	(nodes, edges) = map(int, input().split())
	distances = [-1] * nodes
	graph = [list(distances) for n in range(nodes)]
	for e in range(edges):
		(edge1, edge2, distance) = map(int, input().split())
		edge1 -= 1
		edge2 -= 1
		if graph[edge1][edge2] == -1 or graph[edge1][edge2] > distance:
			graph[edge1][edge2] = distance
			graph[edge2][edge1] = distance
	start_node = int(input()) - 1
	distances[start_node] = 0
	unvisited = set([n for n in range(nodes)])
	current_node = start_node
	while True:
		current_distance = distances[current_node]
		unvisited.remove(current_node)
		for (node, value) in enumerate(graph[current_node]):
			if node in unvisited and value != -1:
				tentative = current_distance + value
				if tentative < distances[node] or distances[node] == -1:
					distances[node] = tentative
		min_dist = float('inf')
		current_node = None
		for node in unvisited:
			if distances[node] > -1 and distances[node] <= min_dist:
				current_node = node
				min_dist = distances[node]
		if current_node == None:
			break
	distances = [str(n) for n in distances]
	print(' '.join(distances[:start_node] + distances[start_node + 1:]))


from heapq import heappush, heappop

class Edge:
	__slots__ = ('origin', 'dest', 'weight')

	def __init__(self, origin, dest, weight):
		self.origin = origin
		self.dest = dest
		self.weight = weight

	def __repr__(self):
		return '{{{}, {}}}'.format(self.origin, self.dest)

	def opposite(self, v):
		return self.dest if v == self.origin else self.origin

class Graph:

	def __init__(self, vertices):
		self.vertices = [[] for i in range(vertices)]

	def insert_edge(self, u, v, w):
		e = Edge(u, v, w)
		self.vertices[u].append(e)
		self.vertices[v].append(e)

	def incident_edges(self, v):
		for edge in self.vertices[v]:
			yield edge
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	g = Graph(N + 1)
	for __ in range(M):
		(x, y, r) = map(int, input().split())
		g.insert_edge(x, y, r)
	S = int(input())
	D = [float('inf')] * (N + 1)
	D[S] = 0
	seen = [False] * (N + 1)
	heap = [(0, S)]
	while heap:
		(d, u) = heappop(heap)
		if not seen[u]:
			seen[u] = True
			for e in g.incident_edges(u):
				v = e.opposite(u)
				if D[u] + e.weight < D[v]:
					D[v] = D[u] + e.weight
					heappush(heap, (D[v], v))
	inf = float('inf')
	print(' '.join([str(v) if v != inf else str(-1) for (i, v) in enumerate(D[1:], 1) if i != S]))


t = int(input())
for _ in range(t):
	wgt = {}
	unchecked = []
	adj = []
	(n, m) = map(int, input().split())
	dist = [4000] * (n + 1)
	for i in range(0, int(n) + 1):
		adj.append([])
	for i in range(m):
		(x, y, w) = map(int, input().split())
		if wgt.get((x, y), 0) == 0:
			adj[x].append(y)
			adj[y].append(x)
			wgt[x, y] = w
			wgt[y, x] = w
		elif wgt.get((x, y), 0) > w:
			wgt[x, y] = w
			wgt[y, x] = w
	s = int(input())
	dist[s] = 0
	for i in range(1, n + 1):
		unchecked.append(i)
	while unchecked != []:
		mi = 40000
		for i in range(len(unchecked)):
			if mi > dist[unchecked[i]]:
				mi = dist[unchecked[i]]
				y = unchecked[i]
		unchecked.remove(y)
		for x in adj[y]:
			if dist[x] > dist[y] + wgt[x, y]:
				dist[x] = dist[y] + wgt[x, y]
	for i in range(1, len(dist)):
		if i != len(dist) - 1:
			if dist[i] != 0:
				if dist[i] == 4000:
					dist[i] = -1
				print(dist[i], end=' ')
		elif dist[i] != 0:
			if dist[i] == 4000:
				dist[i] = -1
			print(dist[i])


from queue import Queue

def dijkstra(graph, s):
	q = Queue()
	q.put(s)
	graph[s][2] = 0
	while not q.empty():
		current = q.get()
		for (x, r) in graph[current][0].items():
			if graph[x][2] == -1 or graph[x][2] > graph[current][2] + graph[current][0][x]:
				graph[x][1] = current
				graph[x][2] = graph[current][2] + graph[current][0][x]
				q.put(x)
for bta3 in range(int(input())):
	(n, m) = map(int, input().split())
	graph = {i: [{}, None, -1] for i in range(1, n + 1)}
	for i in range(m):
		(x, y, r) = map(int, input().split())
		if y in graph[x][0].keys():
			if r > graph[y][0][x]:
				continue
		graph[x][0][y] = r
		graph[y][0][x] = r
	s = int(input())
	dijkstra(graph, s)
	output = ''
	for i in range(1, n + 1):
		if i == s:
			continue
		output += str(graph[i][2]) + ' '
	print(output.strip())


import queue

class Vertex:

	def __init__(self, id, N):
		self.id = id
		self.dist = float('inf')
		self.adjVertex = [-1] * N
		self.known = False
T = int(input())
for i in range(T):
	(N, M) = str(input()).split()
	vertexList = []
	for k in range(int(N)):
		vertexList.append(Vertex(str(k), int(N)))
	for j in range(int(M)):
		(u, v, r) = str(input()).split()
		if vertexList[int(u) - 1].adjVertex[int(v) - 1] == -1:
			vertexList[int(u) - 1].adjVertex[int(v) - 1] = int(r)
			vertexList[int(v) - 1].adjVertex[int(u) - 1] = int(r)
		elif int(r) < vertexList[int(u) - 1].adjVertex[int(v) - 1]:
			vertexList[int(u) - 1].adjVertex[int(v) - 1] = int(r)
			vertexList[int(v) - 1].adjVertex[int(u) - 1] = int(r)
	S = str(input())
	vertexList[int(S) - 1].dist = 0
	u = next((x for x in vertexList if x.known is False), None)
	while u is not None:
		for item in vertexList:
			if item.known is False and item.dist < u.dist:
				u = item
		u.known = True
		for w in range(int(N)):
			if u.adjVertex[w - 1] != -1:
				if vertexList[w - 1].known is False:
					if vertexList[w - 1].dist > u.dist + u.adjVertex[w - 1]:
						vertexList[w - 1].dist = u.dist + u.adjVertex[w - 1]
		u = next((x for x in vertexList if x.known is False), None)
	for vertex in vertexList:
		if vertex.dist == float('inf'):
			vertex.dist = -1
		if vertex.dist != 0:
			print(vertex.dist, end=' ')
	print('')


from collections import defaultdict
INF = float('inf')

def dijkstra(graph, source):
	queue = list()
	(dist, prev) = (dict(), dict())
	for vertex in graph:
		dist[vertex] = float('inf')
		prev[vertex] = None
	dist[source] = 0
	queue.append(source)
	while queue:
		vertex = queue.pop(0)
		for reachable in graph[vertex]:
			dist_to_reachable = dist[vertex] + graph[vertex][reachable]
			if dist[reachable] > dist_to_reachable:
				dist[reachable] = dist_to_reachable
				prev[reachable] = vertex
				queue.append(reachable)
	return (dist, prev)
test_cases = int(input())
for _ in range(test_cases):
	(num_nodes, num_edges) = [int(i) for i in input().split()[:2]]
	graph = defaultdict(dict)
	for _ in range(num_edges):
		(a, b, weight) = [int(i) for i in input().split()[:3]]
		graph[a][b] = min([weight, b in graph[a] and graph[a][b] or INF])
		graph[b][a] = min([weight, a in graph[b] and graph[b][a] or INF])
	root = int(input())
	(dist, prev) = dijkstra(graph, root)
	for i in sorted(dist):
		if dist[i] == 0:
			continue
		if dist[i] == INF:
			print(-1, end=' ')
		else:
			print(dist[i], end=' ')
	print()


class Graph:

	def __init__(self, N, M):
		self.N = N
		self.M = M
		self.adj = {key: list() for key in range(1, N + 1)}
		for m in range(M):
			(u, v, w) = [int(x) for x in input().split()]
			self.adj[u].append((v, w))
			self.adj[v].append((u, w))

	def shortest_distance(self, s):
		dist = {}
		processed = set()
		dist[s] = 0
		v = s
		while v not in processed:
			processed.add(v)
			current_dist = dist[v]
			for (node, weight) in self.adj[v]:
				if node in processed:
					continue
				new_dist = current_dist + weight
				if node not in dist or dist[node] > new_dist:
					dist[node] = new_dist
			min_dist = -1
			for (node, distance) in dist.items():
				if node in processed:
					continue
				if min_dist < 0 or distance < min_dist:
					min_dist = distance
					v = node
		result = []
		for n in range(1, N + 1):
			if n == s:
				continue
			elif n not in dist:
				result.append(-1)
			else:
				result.append(dist[n])
		print(' '.join([str(x) for x in result]))
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	g = Graph(N, M)
	s = int(input())
	g.shortest_distance(s)


def selectWeight(w1, w2):
	ans = w1
	if w1 == 0:
		ans = w2
	elif w1 < w2:
		ans = w1
	else:
		ans = w2
	return ans

def findmin(d, unvisited, n):
	dmin = 10000000
	(i, imin) = (0, 0)
	while i < n:
		if unvisited[i] and dmin > d[i]:
			dmin = d[i]
			imin = i
		i = i + 1
	return imin

def bfs(s, n, e):
	d = [10000000] * n
	unvisited = [True] * n
	d[s - 1] = 0
	count = 0
	while count < n:
		count = count + 1
		src_ = findmin(d, unvisited, n)
		unvisited[src_] = False
		for i in range(n):
			if i < src_:
				if e[i][src_ - i] > 0:
					if unvisited[i] and d[src_] != 10000000:
						d_new = d[src_] + e[i][src_ - i]
						if d_new < d[i]:
							d[i] = d_new
			elif src_ < i:
				if e[src_][i - src_] > 0:
					if unvisited[i] and d[src_] != 10000000:
						d_new = d[src_] + e[src_][i - src_]
						if d_new < d[i]:
							d[i] = d_new
	i = 0
	while i < n:
		if d[i] == 10000000:
			print('-1', end='')
			break
		elif d[i] != 0:
			print(d[i], end='')
			break
		i = i + 1
	for i in range(i + 1, n):
		if d[i] == 10000000:
			print(' -1', end='')
		elif d[i] != 0:
			ans = d[i]
			ans = str(ans)
			ans = ' ' + ans[:]
			print(ans, end='')
	(i, count) = (0, 0)
	while i < 0:
		if unvisited[i]:
			print('-1', end='')
			count = count + 1
		elif d[i] != 0:
			print(d[i], end='')
			count = count + 1
		if d[i] != 0 and count < n - 1:
			print(' ', end='')
		i = i + 1
t = int(input().strip())
while t > 0:
	t = t - 1
	x = input().strip().split()
	(n, m) = (int(x[0]), int(x[1]))
	edge = [[0 for j in range(i)] for i in range(n, 0, -1)]
	while m > 0:
		m = m - 1
		ei = input().strip().split()
		(n1, n2, r) = (int(ei[0]), int(ei[1]), int(ei[2]))
		if n1 > n2:
			edge[n2 - 1][n1 - n2] = selectWeight(edge[n2 - 1][n1 - n2], r)
		elif n2 > n1:
			edge[n1 - 1][n2 - n1] = selectWeight(edge[n1 - 1][n2 - n1], r)
	s = int(input().strip())
	bfs(s, n, edge)
	print()


graph = []

def dijkstra(source, n):
	dist = n * [10 ** 8]
	visited = n * [False]
	dist[source] = 0
	visited[source] = 0
	for _ in range(n - 1):
		for i in range(n):
			if i != source and graph[source][i] > -1:
				dist[i] = min(dist[i], dist[source] + graph[source][i])
		min_dist = 10 ** 8
		for i in range(n):
			if visited[i] == False:
				if min_dist > dist[i]:
					source = i
					min_dist = dist[i]
		visited[source] = True
	result = ''
	for i in dist:
		if i != 0:
			if i == 10 ** 8:
				result = result + ' -1'
			else:
				result = result + ' ' + str(i)
	print(result[1:])
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	graph = [n * [-1] for _ in range(n)]
	for _ in range(m):
		(a, b, l) = map(int, input().split())
		a -= 1
		b -= 1
		if graph[a][b] == -1:
			graph[a][b] = l
			graph[b][a] = l
		elif graph[a][b] > l:
			graph[a][b] = l
			graph[b][a] = l
	source = int(input()) - 1
	dijkstra(source, n)


T = int(input())
for t in range(T):
	(N, M) = [int(i) for i in input().split()]
	neighbors = {v: [] for v in range(1, N + 1)}
	for i in range(M):
		(v1, v2, d) = [int(i) for i in input().split()]
		neighbors[v1].append((v2, d))
		neighbors[v2].append((v1, d))
	S = int(input())
	dist = {S: 0}
	queue = [(S, 0)]
	mark = set([])
	while len(queue) > 0:
		elem = queue.pop(0)
		v = elem[0]
		d = elem[1]
		mark.add(v)
		for (new_v, delta_d) in neighbors[v]:
			if new_v in mark:
				continue
			if new_v not in dist:
				dist[new_v] = d + delta_d
				queue.append((new_v, d + delta_d))
			else:
				dist[new_v] = min(d + delta_d, dist[new_v])
				for (i, q) in enumerate(queue):
					if q[0] == new_v:
						queue[i] = (q[0], dist[new_v])
						break
		queue.sort(key=lambda x: x[1])
	to_print = []
	for i in range(1, N + 1):
		if i == S:
			continue
		elif i in dist:
			to_print.append(dist[i])
		else:
			to_print.append(-1)
	print(' '.join((str(i) for i in to_print)))


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split()]
	adj = [[] for x in range(n)]
	for j in range(m):
		(n1, n2, c) = [int(x) - 1 for x in input().split()]
		c = c + 1
		adj[n1].append((n2, c))
		adj[n2].append((n1, c))
	s = int(input()) - 1
	unvisited = set(range(n))
	visited = set()
	w = [float('Inf')] * n
	w[s] = 0
	while unvisited:
		node = min(unvisited, key=lambda x: w[x])
		if w[node] == float('Inf'):
			break
		for (adjnode, c) in adj[node]:
			if w[adjnode] > w[node] + c:
				w[adjnode] = w[node] + c
		visited.add(node)
		unvisited.remove(node)
	w.pop(s)
	w = ['-1' if x == float('inf') else str(x) for x in w]
	print(' '.join(w))


import heapq
t = int(input())
for _ in range(0, t):
	(n, m) = map(int, input().split())
	g = {}
	for __ in range(0, m):
		(x, y, r) = map(int, input().split())
		x -= 1
		y -= 1
		if x in g and y in g and (y in g[x]):
			if r < g[x][y]:
				g[x][y] = r
				g[y][x] = r
		else:
			if x in g:
				g[x][y] = r
			else:
				g[x] = {y: r}
			if y in g:
				g[y][x] = r
			else:
				g[y] = {x: r}
	s = int(input()) - 1
	dist = [-1 if x != s else 0 for x in range(0, n)]
	visited = [False for _ in range(0, n)]
	heap = [(0, s)]
	while len(heap) > 0:
		(x, k) = heapq.heappop(heap)
		if not visited[k]:
			visited[k] = True
			if k in g:
				for l in g[k]:
					if dist[l] == -1 or dist[l] > dist[k] + g[k][l]:
						dist[l] = dist[k] + g[k][l]
						heapq.heappush(heap, (dist[l], l))
	for i in range(0, n):
		if i != s:
			print(dist[i], end=' ')
	print()


import heapq

class Node(object):

	def __init__(self):
		self.neighbors = set()

class Heap:

	def __init__(self, initial=[], key=lambda x: x):
		self.key = key
		self.entryCount = len(initial)
		self._data = [(key(item), count, item) for (item, count) in zip(initial, range(self.entryCount))]
		heapq.heapify(self._data)

	def pop(self):
		return heapq.heappop(self._data)[2]

	def update(self):
		self._data = [(self.key(item), count, item) for (_, count, item) in self._data]
		heapq.heapify(self._data)

	def __len__(self):
		return len(self._data)

def dijkstra(nodes, start):
	for node in nodes:
		node.distance = float('inf')
		node.previous = None
	start.distance = 0
	minHeap = Heap(initial=nodes, key=lambda node: node.distance)
	while len(minHeap) != 0:
		u = minHeap.pop()
		for neighbor in u.neighbors:
			alt = u.distance + neighbor[1]
			if alt < neighbor[0].distance:
				neighbor[0].distance = alt
				neighbor[0].previous = u
				minHeap.update()
t = int(input())
for i in range(t):
	(n, m) = [int(num) for num in input().split(' ')]
	nodes = [Node() for _ in range(n)]
	for j in range(m):
		(a, b, weight) = [int(num) for num in input().split(' ')]
		nodes[a - 1].neighbors.add((nodes[b - 1], weight))
		nodes[b - 1].neighbors.add((nodes[a - 1], weight))
	s = int(input()) - 1
	start = nodes[s]
	dijkstra(nodes, start)
	print(' '.join([str(node.distance) if node.distance != float('inf') else str(-1) for node in nodes if node != start]))


from heapq import *
tcases = int(input())
for tcase in range(0, tcases):
	(nodes, edges) = [int(x) for x in input().split()]
	graph = []
	minval = []
	for n in range(0, nodes + 1):
		graph.append([])
	minval = []
	for m in range(0, edges):
		(s, e, w) = [int(x) for x in input().split()]
		graph[s].append((e, w))
		graph[e].append((s, w))
	snode = int(input())
	Q = []
	for n in range(0, nodes + 1):
		if n != snode:
			Q.append([float('inf'), n])
			minval.append(float('inf'))
		else:
			Q.append([0, n])
			minval.append(0)
	heapify(Q)
	S = set()
	while len(S) < nodes:
		node = heappop(Q)
		if node[0] == float('inf'):
			break
		S.add(node[1])
		for e in graph[node[1]]:
			if e[0] not in S and minval[node[1]] + e[1] < minval[e[0]]:
				for i in range(0, len(Q)):
					if Q[i][1] == e[0]:
						Q[i][0] = minval[node[1]] + e[1]
						minval[e[0]] = Q[i][0]
						heapify(Q)
						break
	for i in range(1, nodes + 1):
		if minval[i] == float('inf'):
			minval[i] = -1
		if i == snode:
			continue
		print(str(minval[i]) + ' ', end='')
	print('')


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import heapq

class Graph:

	def __init__(self, vertexCount):
		self.vertexCount = vertexCount
		self.nodes = []
		for v in range(vertexCount):
			self.nodes.append(node(v))

	def addEdge(self, x, y, w):
		self.nodes[y].addEdge(x, w)
		self.nodes[x].addEdge(y, w)

	def Dijkstra(self, start):
		self.nodes[start].d = 0
		queue = [v for v in self.nodes]
		heapq.heapify(queue)
		while len(queue):
			u = heapq.heappop(queue)
			self.nodes[u.nodeNumber].visited = 1
			for v in u.adjacentList.keys():
				self.Relax(u.nodeNumber, v)
			heapq.heapify(queue)

	def Relax(self, u, v):
		if self.nodes[v].d > self.nodes[u].d + self.nodes[u].adjacentList[v]:
			self.nodes[v].d = self.nodes[u].d + self.nodes[u].adjacentList[v]
			self.nodes[v].pi = u

class node:

	def __init__(self, nodeNumber):
		self.nodeNumber = nodeNumber
		self.d = float('inf')
		self.pi = -1
		self.visited = 0
		self.adjacentList = {}

	def addEdge(self, y, w):
		try:
			if self.adjacentList[y] > w:
				self.adjacentList[y] = w
		except KeyError:
			self.adjacentList[y] = w

	def __lt__(self, other):
		return self.d < other.d
T = int(input())
for t in range(T):
	[N, M] = list(map(int, input().split()))
	graph = Graph(N)
	for m in range(M):
		[x, y, w] = list(map(int, input().split()))
		graph.addEdge(x - 1, y - 1, w)
	graph.Dijkstra(int(input()) - 1)
	for i in range(N):
		if graph.nodes[i].d == 0:
			continue
		elif graph.nodes[i].d < float('inf'):
			print(graph.nodes[i].d, end=' ')
		else:
			print(-1, end=' ')
	print('')


infinite = float('inf')
n_tests = int(input())
for t in range(n_tests):
	(n_nodes, n_edges) = map(int, input().split()[:2])
	edges = []
	for m in range(n_edges):
		(a, b, w) = map(int, input().split()[:3])
		edges.extend([(a - 1, b - 1, w), (b - 1, a - 1, w)])
	s = int(input()) - 1
	dist = [infinite] * n_nodes
	dist[s] = 0
	for i in range(n_nodes - 1):
		changed = False
		for (a, b, w) in edges:
			aux = dist[a] + w
			if aux < dist[b]:
				dist[b] = aux
				changed = True
		if not changed:
			break
	print(*(dist[a] if dist[a] < infinite else -1 for a in range(n_nodes) if a != s))


import heapq

def find(V, N, S):
	dist = [-1 for x in range(N)]
	visited = [False for x in range(N)]
	Q = [(0, S)]
	dist[S] = 0
	while Q:
		(mindist, minv) = heapq.heappop(Q)
		if not visited[minv]:
			for x in V[minv]:
				if dist[x] == -1:
					dist[x] = mindist + V[minv][x]
				else:
					dist[x] = min(dist[x], mindist + V[minv][x])
				heapq.heappush(Q, (dist[x], x))
			visited[minv] = True
	del dist[S]
	for x in dist:
		print(x, end=' ')
	print()

def update(V, X, Y, R):
	if Y not in V[X]:
		V[X][Y] = R
	else:
		V[X][Y] = min(V[X][Y], R)
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	V = [dict() for x in range(N)]
	for i in range(M):
		(X, Y, R) = (int(x) for x in input().split())
		(X, Y) = (X - 1, Y - 1)
		update(V, X, Y, R)
		update(V, Y, X, R)
	find(V, N, int(input()) - 1)


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


def dijkstra(start, n, edges, weights):
	dist = [99999999999999] * n
	q = [i for i in range(n)]
	dist[start] = 0
	while q != []:
		u = -1
		mindist = 999999999999999
		for uu in q:
			if dist[uu] < mindist:
				u = uu
				mindist = dist[uu]
		q.remove(u)
		for v in edges[u]:
			newdist = dist[u] + weights[u][v]
			dist[v] = newdist if newdist < dist[v] else dist[v]
	return [x if x != 99999999999999 else -1 for x in dist]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	edges = [[] for _ in range(n)]
	weights = [[999999999999999 for _ in range(n)] for _ in range(n)]
	for _ in range(m):
		(x, y, r) = map(int, input().split())
		weights[x - 1][y - 1] = min(weights[x - 1][y - 1], r)
		weights[y - 1][x - 1] = min(weights[y - 1][x - 1], r)
		if y - 1 in edges[x - 1] or x - 1 in edges[y - 1]:
			continue
		edges[x - 1].append(y - 1)
		edges[y - 1].append(x - 1)
	start = int(input())
	ans = [str(x) for x in dijkstra(start - 1, n, edges, weights)]
	print(' '.join(ans[:start - 1] + ans[start:]))


from sys import maxsize
cases = int(input())
for _ in range(cases):
	(node_amt, edge_amt) = [int(_x) for _x in input().split()]
	adj_matrix = [[None for _i in range(node_amt)] for _j in range(node_amt)]
	for _i in range(edge_amt):
		(x, y, r) = [int(_x) for _x in input().split()]
		if adj_matrix[x - 1][y - 1] != None:
			adj_matrix[x - 1][y - 1] = r if r < adj_matrix[x - 1][y - 1] else adj_matrix[x - 1][y - 1]
		else:
			adj_matrix[x - 1][y - 1] = r
		if adj_matrix[y - 1][x - 1] != None:
			adj_matrix[y - 1][x - 1] = r if r < adj_matrix[y - 1][x - 1] else adj_matrix[y - 1][x - 1]
		else:
			adj_matrix[y - 1][x - 1] = r
	s = int(input()) - 1
	adj_matrix[s][s] = 0

	def adjacent_nodes(node):
		return [i for i in range(node_amt) if adj_matrix[node][i] != None]

	def dijkstra(node):
		vertex_set = set()
		distance = {}
		prev = {}
		for i in range(node_amt):
			distance[i] = maxsize
			prev[i] = None
			vertex_set.add(i)
		distance[node] = 0
		while vertex_set:
			u = min(vertex_set, key=distance.get)
			vertex_set.remove(u)
			for v in adjacent_nodes(u):
				alt = distance[u] + adj_matrix[u][v]
				if alt < distance[v]:
					distance[v] = alt
					prev[v] = u
		return distance
	result = dijkstra(s)
	print(' '.join([str(result[i] if result[i] != maxsize else -1) for i in range(node_amt) if i != s]))


def distance(nodes, edges, start_point):
	dist = {}
	dist[start_point] = 0
	for node in nodes:
		if node != start_point:
			dist[node] = 0
	reach_points = {start_point}
	ch = 1
	while ch != 0:
		ch = 0
		for edge in edges:
			if edge[0] in reach_points:
				if edge[1] not in reach_points:
					dist[edge[1]] = dist[edge[0]] + edge[2]
					ch += 1
				elif edge[1] in reach_points:
					if dist[edge[0]] > dist[edge[1]] + edge[2]:
						dist[edge[0]] = dist[edge[1]] + edge[2]
						ch += 1
					elif dist[edge[1]] > dist[edge[0]] + edge[2]:
						dist[edge[1]] = dist[edge[0]] + edge[2]
						ch += 1
				reach_points.add(edge[1])
			elif edge[0] not in reach_points:
				if edge[1] in reach_points:
					dist[edge[0]] = dist[edge[1]] + edge[2]
					ch += 1
					reach_points.add(edge[0])
	for node in nodes:
		if node not in reach_points:
			dist[node] = -1
	return dist
test_number = int(input().strip())
for j in range(test_number):
	(node_number, edge_number) = tuple((int(i) for i in input().strip().split()))
	nodes = set(range(1, node_number + 1))
	edges = set()
	for i in range(edge_number):
		edges.add(tuple((int(i) for i in input().strip().split())))
	start_point = int(input().strip())
	distances = distance(nodes, edges, start_point)
	output = tuple((str(distances[node]) for node in nodes if node != start_point))
	print(' '.join(output))


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


from heapq import *
from collections import defaultdict

def add(adjList, fr, to):
	adjList[fr].append(to)

def setWeight(weights, node1, node2, weight):
	weights[node1][node2] = weight
	weights[node2][node1] = weight

def addPair(adjList, node1, node2):
	add(adjList, node1, node2)
	add(adjList, node2, node1)

def addEdge(adjList, weights, node1, node2, weight):
	existingWeight = weights[node1][node2]
	if existingWeight == -1 or weight < existingWeight:
		setWeight(weights, node1, node2, weight)
		if existingWeight == -1:
			addPair(adjList, node1, node2)

def extractMin(pq):
	pair = heappop(pq)
	(priority, node) = (pair[0], pair[1])
	while pq and node == 'R':
		pair = heappop(pq)
		(priority, node) = (pair[0], pair[1])
	return node

def dijkstra(start, adjList, weights, vertices):
	dist = [-1 for v in range(vertices + 1)]
	visited = {}
	vMap = {}
	pq = []
	dist[start] = 0
	startNode = [0, str(start)]
	heappush(pq, startNode)
	vMap[start] = startNode
	while pq:
		node = extractMin(pq)
		if node == 'R':
			break
		node = int(node)
		if node not in visited:
			visited[node] = True
		else:
			continue
		if adjList[node]:
			neighbours = adjList[node]
			for neighbour in neighbours:
				if neighbour in visited:
					continue
				weight = weights[node][neighbour]
				if dist[neighbour] == -1 or dist[node] + weight < dist[neighbour]:
					dist[neighbour] = dist[node] + weight
					pair = [dist[neighbour], str(neighbour)]
					if neighbour not in vMap:
						vMap[neighbour] = pair
					else:
						vMap[neighbour][-1] = 'R'
						vMap[neighbour] = pair
					heappush(pq, pair)
	return list(map(lambda d: str(d), dist))
testCases = int(input())
for testCase in range(testCases):
	params = input().split(' ')
	(vertices, edges) = (int(params[0]), int(params[1]))
	adjList = defaultdict(list)
	weights = [[-1 for v in range(vertices + 1)] for vertex in range(vertices + 1)]
	for edge in range(edges):
		edgeInfo = input().split(' ')
		(node1, node2, weight) = (int(edgeInfo[0]), int(edgeInfo[1]), int(edgeInfo[2]))
		addEdge(adjList, weights, node1, node2, weight)
	start = int(input())
	shortestPaths = dijkstra(start, adjList, weights, vertices)
	ans = shortestPaths[1:start] + shortestPaths[start + 1:]
	print(' '.join(ans))


import heapq
from collections import namedtuple
Item = namedtuple('Item', ['r', 'n'])

def solve(t, n, m, es, s):
	dist = [-1] * n
	dist[s - 1] = 0
	bq = [Item(0, s)]
	heapq.heapify(bq)
	while 0 < len(bq):
		current = heapq.heappop(bq)
		for item in es[current.n]:
			if dist[item.n - 1] == -1 or dist[item.n - 1] > dist[current.n - 1] + item.r:
				dist[item.n - 1] = dist[current.n - 1] + item.r
				heapq.heappush(bq, Item(item.r, item.n))
	return dist[:s - 1] + dist[s:]

def main():
	(N, M) = (int(v) for v in input().split())
	ES = [set() for _ in range(N + 1)]
	for _ in range(M):
		(start, end, r) = (int(v) for v in input().split())
		ES[start].add(Item(r, end))
		ES[end].add(Item(r, start))
	S = int(input())
	print(' '.join(map(lambda x: str(x), solve(T, N, M, ES, S))))
T = int(input())
for _ in range(T):
	main()


def dijkstra(graph, start):
	(spt_set, dists) = (set(), {node: 0 if node == start else float('inf') for node in list(graph)})
	while not spt_set == set(list(graph)):
		nearest = (None, float('inf'))
		for node in dists:
			if nearest[1] > dists[node] and spt_set.isdisjoint([node]):
				nearest = (node, dists[node])
		spt_set.add(nearest[0])
		try:
			neighbours = graph[nearest[0]]
		except Exception as e:
			for node in dists:
				dists[node] = -1 if dists[node] == float('inf') else dists[node]
			return dists
		for node in graph[nearest[0]]:
			if dists[node[0]] > nearest[1] + node[1]:
				dists[node[0]] = nearest[1] + node[1]
	return dists
t = int(input())
cases = []
for i in range(t):
	(nodes, edges) = [int(i) for i in input().split()]
	graph = {x: set([]) for x in range(1, nodes + 1)}
	for j in range(edges):
		(f, t, w) = [int(i) for i in input().split()]
		graph[f].add((t, w))
		graph[t].add((f, w))
	start = int(input())
	cases.append((nodes, edges, graph, start))
for case in cases:
	lens = dijkstra(case[2], case[3])
	result = [str(lens[i]) for i in lens if not i == case[3]]
	print(' '.join(result))


import queue

class MyEdge:

	def __init__(self, node, edgeLength):
		self.nbr = node
		self.length = edgeLength

class MyNode:

	def __init__(self):
		self.dist = -1
		self.edges = []

def breadthFirst(nodeQueue):
	while not nodeQueue.empty():
		current = nodeQueue.get()
		for edge in current.edges:
			if edge.nbr.dist == -1 or edge.nbr.dist > current.dist + edge.length:
				edge.nbr.dist = current.dist + edge.length
				nodeQueue.put(edge.nbr)

def calculateDistances(node):
	myQueue = queue.Queue(0)
	node.dist = 0
	myQueue.put(node)
	breadthFirst(myQueue)
T = int(input())
for t in range(T):
	(numNodes, numEdges) = [int(x) for x in input().split()]
	graph = []
	for _ in range(numNodes):
		graph.append(MyNode())
	for _ in range(numEdges):
		(a, b, length) = [int(x) for x in input().split()]
		(a, b) = (a - 1, b - 1)
		graph[a].edges.append(MyEdge(graph[b], length))
		graph[b].edges.append(MyEdge(graph[a], length))
	s = int(input()) - 1
	calculateDistances(graph[s])
	del graph[s]
	print(' '.join([str(node.dist) for node in graph]))


import heapq

class PriorityQueue(list):

	def add(self, priority, item):
		heapq.heappush(self, (priority, item))

	def remove(self):
		return heapq.heappop(self)

class Graph:

	def __init__(self, N):
		self.N = N
		self.adj = [[] for _ in range(N + 1)]

	def add_edge(self, node1, node2, weight):
		self.adj[node1].append((node2, weight))

	def neighbours(self, node):
		return iter(self.adj[node])

def search(start, graph):
	distances = [-1] * (graph.N + 1)
	frontier = PriorityQueue()
	frontier.add(0, start)
	visited = set()
	while frontier:
		(distance, node) = frontier.remove()
		if node not in visited:
			distances[node] = distance
			visited.add(node)
			for (next_node, d) in graph.neighbours(node):
				frontier.add(distance + d, next_node)
	return distances
for _ in range(int(input())):
	(N, M) = input().split()
	(N, M) = (int(N), int(M))
	graph = Graph(N)
	for _ in range(M):
		(n1, n2, r) = tuple(map(int, input().split()))
		graph.add_edge(n1, n2, r)
		graph.add_edge(n2, n1, r)
	start = int(input())
	for dist in search(start, graph)[1:]:
		if dist != 0:
			print(dist, end=' ')
	print()


import heapq
t = int(input())
for l in range(t):
	(n, m) = map(int, input().split())
	a = [[] for i in range(n + 1)]
	an = [-1 for i in range(n + 1)]
	al = [0 for i in range(n + 1)]
	q = []
	heapq.heapify(q)
	for i in range(m):
		(x, y, r) = map(int, input().split())
		a[x].append((y, r))
		a[y].append((x, r))
	s = int(input())
	heapq.heappush(q, (0, s))
	an[s] = 0
	while q:
		v = heapq.heappop(q)
		if not al[v[1]]:
			an[v[1]] = v[0]
			al[v[1]] = 1
		for i in a[v[1]]:
			if not al[i[0]]:
				x = an[v[1]] + i[1]
				heapq.heappush(q, (x, i[0]))
	an.pop(s)
	an.pop(0)
	for x in an:
		print(x, end=' ')
	print('')


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


from collections import defaultdict
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	graph = defaultdict(list)
	weights = dict()
	for _ in range(M):
		(n1, n2, w) = map(int, input().split(' '))
		graph[n1].append(n2)
		graph[n2].append(n1)
		weights[n1, n2] = min(weights.get((n1, n2), w), w)
		weights[n2, n1] = min(weights.get((n2, n1), w), w)
	S = int(input())
	node_visiting = S
	nodes_visited = set()
	nodes_boundary = set()
	dist = [350 * M] * (N + 1)
	dist[S] = 0
	while True:
		for node_adj in graph[node_visiting]:
			if node_adj not in nodes_visited:
				nodes_boundary.add(node_adj)
				if dist[node_adj] > dist[node_visiting] + weights[node_visiting, node_adj]:
					dist[node_adj] = dist[node_visiting] + weights[node_visiting, node_adj]
		nodes_visited.add(node_visiting)
		if nodes_boundary:
			node_visiting = min(nodes_boundary, key=dist.__getitem__)
			nodes_boundary.remove(node_visiting)
		else:
			break
	dist.pop(S)
	dist.pop(0)
	print(' '.join(map(str, dist)).replace(str(350 * M), str(-1)))


import heapq

class Node:

	def __init__(self, label):
		self.label = label
		self.adjacent_nodes = set()
		self.distance = float('inf')
		self.previous = None

def build_graph():
	graph = dict()
	(nodes, edges) = tuple((int(number) for number in input().split()))
	for label in range(1, nodes + 1):
		node = Node(label)
		graph[label] = node
	for _ in range(edges):
		(first, second, dist) = tuple((int(number) for number in input().split()))
		graph[first].adjacent_nodes.add((graph[second], dist))
		graph[second].adjacent_nodes.add((graph[first], dist))
	return graph

def calculate_distances(start_node, graph):
	queue = list()
	start_node.distance = 0
	heapq.heappush(queue, (0, start_node.label))
	while queue:
		(_, node_label) = heapq.heappop(queue)
		node = graph[node_label]
		for (adjacent_node, dist) in node.adjacent_nodes:
			alt = node.distance + dist
			if alt < adjacent_node.distance:
				adjacent_node.distance = alt
				adjacent_node.previous = node
				node_to_enqueue = (adjacent_node.distance, adjacent_node.label)
				if node_to_enqueue not in queue:
					heapq.heappush(queue, node_to_enqueue)

def print_distances(start_node, graph):
	distances = list()
	for label in range(1, len(graph.keys()) + 1):
		node = graph[label]
		if node == start_node:
			continue
		distances.append(str(node.distance) if node.distance != float('inf') else '-1')
	print(' '.join(distances))
for _ in range(int(input())):
	graph = build_graph()
	start_node = graph[int(input())]
	calculate_distances(start_node, graph)
	print_distances(start_node, graph)


t = int(input())
for x in range(t):
	(n, m) = list(map(int, input().split(' ')))
	edges = [[] for y in range(n)]
	for y in range(m):
		(a, b, r) = list(map(int, input().split(' ')))
		edges[a - 1].append([b - 1, r])
		edges[b - 1].append([a - 1, r])
	s = int(input())
	length = [350 * n for y in range(n)]
	length[s - 1] = 0
	nodes = [y for y in range(n)]
	current = s - 1
	min_ = 0
	while len(nodes) > 0:
		nodes.remove(current)
		j = current
		for y in edges[current]:
			if length[current] + y[1] < length[y[0]]:
				length[y[0]] = length[current] + y[1]
		min_ = 350 * n
		for y in nodes:
			if length[y] < min_:
				min_ = length[y]
				j = y
		if j == current:
			break
		else:
			current = j
	for y in range(len(length)):
		if length[y] == 350 * n:
			length[y] = -1
	for y in length[:s - 1]:
		print(y, end=' ')
	for y in length[s:]:
		print(y, end=' ')
	print()


t = int(input())
while t != 0:
	(n, e) = [int(i) for i in input().split()]
	gr = []
	for i in range(n):
		gr.append(n * [999999])
	for i in range(e):
		(a, b, w) = [int(i) for i in input().split()]
		gr[a - 1][b - 1] = min(w, gr[a - 1][b - 1])
		gr[b - 1][a - 1] = min(w, gr[b - 1][a - 1])
	h = int(input())
	sh = n * [999999]
	done = n * [-1]
	l = h - 1
	d = 0
	sh[l] = 0
	done[l] = 1
	for i in range(n):
		mm = 999999
		for j in range(n):
			sh[j] = min(gr[l][j] + d, sh[j])
		for j in range(n):
			if sh[j] <= mm and done[j] != 1:
				mm = sh[j]
				l = j
				d = sh[j]
		done[l] = 1
	for i in range(n):
		if i != h - 1:
			if sh[i] == 999999:
				print('-1', end=' ')
				continue
			print(sh[i], end=' ')
	t -= 1
	print()


def dijkstra(graph, start):
	(spt_set, dists) = (set(), {node: 0 if node == start else float('inf') for node in list(graph)})
	while not spt_set == set(list(graph)):
		nearest = (None, float('inf'))
		for node in dists:
			if nearest[1] > dists[node] and spt_set.isdisjoint([node]):
				nearest = (node, dists[node])
		spt_set.add(nearest[0])
		try:
			neighbours = graph[nearest[0]]
		except Exception as e:
			for node in dists:
				dists[node] = -1 if dists[node] == float('inf') else dists[node]
			return dists
		for node in graph[nearest[0]]:
			if dists[node[0]] > nearest[1] + node[1]:
				dists[node[0]] = nearest[1] + node[1]
	return dists
t = int(input())
cases = []
for i in range(t):
	(nodes, edges) = [int(i) for i in input().split()]
	graph = {x: set([]) for x in range(1, nodes + 1)}
	for j in range(edges):
		(f, t, w) = [int(i) for i in input().split()]
		graph[f].add((t, w))
		graph[t].add((f, w))
	start = int(input())
	cases.append((nodes, edges, graph, start))
for case in cases:
	lens = dijkstra(case[2], case[3])
	result = [str(lens[i]) for i in lens if not i == case[3]]
	print(' '.join(result))


import heapq

def find(V, N, S):
	dist = [-1 for x in range(N)]
	visited = [False for x in range(N)]
	Q = [(0, S)]
	dist[S] = 0
	while Q:
		(mindist, minv) = heapq.heappop(Q)
		if not visited[minv]:
			for x in V[minv]:
				if dist[x] == -1:
					dist[x] = mindist + V[minv][x]
				else:
					dist[x] = min(dist[x], mindist + V[minv][x])
				heapq.heappush(Q, (dist[x], x))
			visited[minv] = True
	del dist[S]
	for x in dist:
		print(x, end=' ')
	print()

def update(V, X, Y, R):
	if Y not in V[X]:
		V[X][Y] = R
	else:
		V[X][Y] = min(V[X][Y], R)
T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split())
	V = [dict() for x in range(N)]
	for i in range(M):
		(X, Y, R) = (int(x) for x in input().split())
		(X, Y) = (X - 1, Y - 1)
		update(V, X, Y, R)
		update(V, Y, X, R)
	find(V, N, int(input()) - 1)


import collections
import heapq
import queue
import unittest
Edge = collections.namedtuple('Edge', ['cost', 'start', 'destination'])

class Graph(object):

	def __init__(self):
		self.nodes = set()
		self.edges = collections.defaultdict(list)

	def add_node(self, node):
		self.nodes.add(node)

	def add_edge(self, vertex1, vertex2, cost):
		self.nodes.add(vertex1)
		self.nodes.add(vertex2)
		self.edges[vertex1].append(Edge(cost=cost, start=vertex1, destination=vertex2))
		self.edges[vertex2].append(Edge(cost=cost, start=vertex2, destination=vertex1))

	@staticmethod
	def from_edges(edges):
		graph = Graph()
		for (start, end, cost) in edges:
			graph.add_edge(start, end, cost)
		return graph
VertexPriority = collections.namedtuple('VertexPriority', ['cost', 'vertex'])

def find_shortest_path(graph, start):
	travel_costs = {node: float('+inf') for node in graph.nodes}
	travel_costs[start] = 0
	nodes_visited = set()
	frontier = queue.PriorityQueue()
	frontier.put(VertexPriority(cost=0, vertex=start))
	while not frontier.empty():
		(_cost, node_current) = frontier.get()
		node_cost = travel_costs[node_current]
		if node_current in nodes_visited:
			continue
		else:
			nodes_visited.add(node_current)
		for edge in graph.edges[node_current]:
			if edge.destination in nodes_visited:
				continue
			destination_cost = min(node_cost + edge.cost, travel_costs[edge.destination])
			frontier.put(VertexPriority(cost=destination_cost, vertex=edge.destination))
			travel_costs[edge.destination] = destination_cost
	for (node, cost) in travel_costs.items():
		if cost == float('+inf'):
			travel_costs[node] = -1
	return travel_costs

class TestDijkstra(unittest.TestCase):

	def test_2_node_graph(self):
		graph = Graph.from_edges([(1, 2, 7)])
		expected = {1: 0, 2: 7}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_2_node_graph_edges_reveresed(self):
		graph = Graph.from_edges([(2, 1, 7)])
		expected = {1: 0, 2: 7}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_2_node_graph_disconnected(self):
		graph = Graph()
		graph.add_node(1)
		graph.add_node(2)
		expected = {1: 0, 2: -1}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_2_node_graph_1_repeated_edges(self):
		graph = Graph.from_edges([(1, 2, 7), (1, 2, 3)])
		expected = {1: 0, 2: 3}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_2_node_graph_1_repeated_edges_different_start(self):
		graph = Graph.from_edges([(1, 2, 7), (1, 2, 3)])
		expected = {1: 3, 2: 0}
		self.assertEqual(find_shortest_path(graph, start=2), expected)

	def test_2_node_graph_2_repeated_edges(self):
		graph = Graph.from_edges([(1, 2, 7), (1, 2, 5), (1, 2, 9)])
		expected = {1: 0, 2: 5}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_3_node_graph(self):
		graph = Graph.from_edges([(1, 2, 7), (2, 3, 5)])
		expected = {1: 0, 2: 7, 3: 12}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_3_node_graph_2_repeated_edges(self):
		graph = Graph.from_edges([(1, 2, 7), (1, 2, 8), (2, 3, 5), (2, 3, 3)])
		expected = {1: 0, 2: 7, 3: 10}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

	def test_3_node_graph_2_paths_to_last_node(self):
		graph = Graph.from_edges([(1, 2, 7), (1, 2, 8), (2, 3, 5), (2, 3, 3), (1, 3, 2)])
		expected = {1: 0, 2: 5, 3: 2}
		self.assertEqual(find_shortest_path(graph, start=1), expected)

def main():
	num_cases = int(input())
	for _ in range(num_cases):
		graph = Graph()
		(_num_nodes, num_edges) = [int(x) for x in input().split()]
		for _ in range(num_edges):
			(vertex1, vertex2, cost) = [int(x) for x in input().split()]
			graph.add_edge(vertex1, vertex2, cost)
		start_vertex = int(input())
		answer = find_shortest_path(graph, start_vertex)
		answer_without_start = [(node, str(cost)) for (node, cost) in answer.items() if node != start_vertex]
		print(' '.join([cost for (_, cost) in sorted(answer_without_start)]))
main()


from collections import deque

class Nodes(list):

	def __init__(self, e, r):
		self.e = e
		self.r = r
		self.d = -1
for _ in range(int(input())):
	(N, M) = [int(x) for x in input().split()]
	nodes = [Nodes([], []) for _ in range(N)]
	for __ in range(M):
		(i, j, r) = [int(x) - 1 for x in input().split()]
		nodes[i].e.append(j)
		nodes[i].r.append(r + 1)
		nodes[j].e.append(i)
		nodes[j].r.append(r + 1)
	S = int(input()) - 1
	nodes[S].d = 0
	queue = deque([S])
	while len(queue) != 0:
		loc = nodes[queue.popleft()]
		for i in range(len(loc.e)):
			if nodes[loc.e[i]].d > loc.d + loc.r[i] or nodes[loc.e[i]].d == -1:
				nodes[loc.e[i]].d = loc.d + loc.r[i]
				queue.append(loc.e[i])
	print(' '.join([str(x.d) for x in nodes[:S] + nodes[S + 1:]]))


from queue import PriorityQueue

def bfs(nodes, edges, start):
	queue = PriorityQueue()
	dists = {i: -1 for i in range(1, nodes + 1)}
	queue.put((0, start))
	dists[start] = 0
	while not queue.empty():
		(_, node) = queue.get()
		for (next, cost) in edges[node]:
			if dists[next] < 0 or dists[next] > dists[node] + cost:
				dists[next] = dists[node] + cost
				queue.put((dists[next], next))
	return dists
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	edges = {i: [] for i in range(1, N + 1)}
	for _ in range(M):
		(x, y, r) = map(int, input().split())
		edges[x].append((y, r))
		edges[y].append((x, r))
	S = int(input())
	print(' '.join([str(d) for (i, d) in bfs(N, edges, S).items() if i != S]))


from math import isinf
from collections import deque

def find_dist_djikstra(graph, target):
	distances = [float('inf') for n in graph]
	not_visited = [n for n in graph]
	distances[target] = 0
	while len(not_visited) > 0:
		shortest = min([(i, distances[i]) for i in not_visited], key=lambda x: x[1])[0]
		not_visited.remove(shortest)
		for edge in graph[shortest]:
			distances[edge[0]] = min(distances[shortest] + edge[1], distances[edge[0]])
	del distances[target]
	return [-1 if isinf(x) else x for x in distances]
T = int(input())
for t in range(T):
	dists = list()
	inp = list(map(int, input().split()))
	N = inp[0]
	M = inp[1]
	graph = {m: [] for m in range(N)}
	for m in range(M):
		inp = list(map(int, input().split()))
		dist = inp[2] if len(inp) > 2 else 6
		graph[inp[0] - 1].append((inp[1] - 1, dist))
		graph[inp[1] - 1].append((inp[0] - 1, dist))
	S = int(input()) - 1
	nodes_to_test = [x for x in range(N) if x != S]
	print(' '.join(map(str, find_dist_djikstra(graph, S))))


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import heapq
cases = int(input())
alreadyFound = {}

def dijkstra(graph, start, end):
	(weight, solved) = (0, {})
	unvisited = [(0, start)]
	if end in alreadyFound:
		return alreadyFound[end]
	while len(unvisited):
		(weight, node) = heapq.heappop(unvisited)
		if node == end:
			return weight
		if node in solved:
			continue
		alreadyFound[node] = weight
		solved[node] = weight
		for neighbour in graph[node]:
			(nweight, nnode) = neighbour
			if nnode in solved:
				continue
			nweight += weight
			heapq.heappush(unvisited, (nweight, nnode))
	return -1
for i in range(cases):
	(graph, alreadyFound) = ({}, {})
	(nodes, vertices) = [int(x) for x in input().split()]
	for i in range(1, nodes + 1):
		graph[i] = []
	for i in range(vertices):
		(node1, node2, weight) = [int(x) for x in input().split()]
		graph[node1].append((weight, node2))
		graph[node2].append((weight, node1))
	start = int(input())
	for i in range(1, nodes + 1):
		if i != start:
			print(dijkstra(graph, start, i), end=' ')
	print()


import heapq
from heapq import heappush, heappop

def dijkstra(x_to_ys_dict, S, xy_to_edgelen):
	v_to_pathlen = [99999] * (len(x_to_ys_dict) + 1)
	q = [(0, S)]
	visited = set()
	v_to_pathlen[S] = 0
	visited.add((0, S))
	while q:
		(pathlen, curr) = heappop(q)
		for neighbor in x_to_ys_dict[curr]:
			v_to_pathlen[neighbor] = min(v_to_pathlen[neighbor], v_to_pathlen[curr] + xy_to_edgelen[curr, neighbor])
			if not (v_to_pathlen[neighbor], neighbor) in visited:
				heappush(q, (v_to_pathlen[neighbor], neighbor))
				visited.add((v_to_pathlen[neighbor], neighbor))
	ret = []
	for i in range(1, len(v_to_pathlen)):
		if i != S:
			ret.append(str(v_to_pathlen[i]) if v_to_pathlen[i] < 99999 else '-1')
	return ' '.join(ret)
T = int(input())
for _ in range(T):
	(N, M) = tuple([int(x) for x in input().strip().split()])
	x_to_ys_dict = dict()
	xy_to_edgelen_dict = dict()
	for i in range(N):
		x_to_ys_dict[i + 1] = set()
	for _ in range(M):
		(x, y, dist) = tuple([int(x) for x in input().strip().split()])
		x_to_ys_dict[x].add(y)
		x_to_ys_dict[y].add(x)
		xy_to_edgelen_dict[x, y] = min(xy_to_edgelen_dict[x, y], dist) if (x, y) in xy_to_edgelen_dict else dist
		xy_to_edgelen_dict[y, x] = min(xy_to_edgelen_dict[y, x], dist) if (y, x) in xy_to_edgelen_dict else dist
	S = int(input())
	print(dijkstra(x_to_ys_dict, S, xy_to_edgelen_dict))


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


inf = float('inf')
t = int(input())
for tt in range(t):
	(n, m) = map(int, input().split())
	edges = [[inf for j in range(n)] for i in range(n)]
	for i in range(m):
		(u, v, r) = map(int, input().split())
		edges[u - 1][v - 1] = min(r, edges[u - 1][v - 1])
		edges[v - 1][u - 1] = min(r, edges[v - 1][u - 1])
	curr_node = int(input()) - 1
	visited = [0 for i in range(n)]
	distances = [inf for i in range(n)]
	distances[curr_node] = 0
	while True:
		for i in range(len(edges[curr_node])):
			if edges[curr_node][i] != inf and distances[curr_node] + edges[curr_node][i] < distances[i]:
				distances[i] = distances[curr_node] + edges[curr_node][i]
		visited[curr_node] = 1
		min_dist = inf
		for i in range(n):
			if visited[i] == 0 and distances[i] < min_dist:
				curr_node = i
				min_dist = distances[i]
		if min_dist == inf:
			break
	for dist in distances:
		if dist != 0:
			if dist == inf:
				print('-1 ', end='')
			else:
				print(str(dist) + ' ', end='')
	print('')


def dijkstra(graph, nnodes, start_node):
	plens = [-1 for n in range(nnodes)]
	stop = [False for n in range(nnodes)]
	cnode = start_node
	clen = 0
	while True:
		mlen = 0
		stop[cnode] = True
		for i in range(nnodes):
			if graph[cnode][i] != -1 and (not stop[i]):
				if plens[i] == -1 or graph[cnode][i] + clen <= plens[i]:
					plens[i] = graph[cnode][i] + clen
			if plens[i] > mlen:
				mlen = plens[i]
		tlen = mlen
		tnode = cnode
		all_stop = True
		for i in range(nnodes):
			if not stop[i] and plens[i] != -1 and (plens[i] <= tlen):
				tnode = i
				tlen = plens[i]
			all_stop = all_stop and stop[i]
		if tnode == cnode or all_stop:
			break
		cnode = tnode
		clen = plens[cnode]
	return plens[0:start_node] + plens[start_node + 1:]
ncases = int(input())
for unused_nc in range(ncases):
	(nnodes, nedges) = tuple([int(n) for n in input().strip().split(' ')])
	graph = [[-1 for i in range(nnodes)] for j in range(nnodes)]
	for unused_ne in range(nedges):
		(sedge, eedge, weight) = tuple([int(n) for n in input().strip().split(' ')])
		c1 = graph[sedge - 1][eedge - 1] != -1 and graph[sedge - 1][eedge - 1] >= weight
		c2 = graph[sedge - 1][eedge - 1] == -1
		if c1 or c2:
			graph[sedge - 1][eedge - 1] = weight
			graph[eedge - 1][sedge - 1] = weight
	snode = int(input()) - 1
	print(' '.join([str(n) for n in dijkstra(graph, nnodes, snode)]))


import heapq
T = int(input())

def solve():
	(N, M) = map(int, input().split())
	g = [[] for _ in range(N)]
	for _ in range(M):
		(x, y, r) = map(int, input().split())
		g[x - 1].append((y - 1, r))
		g[y - 1].append((x - 1, r))
	S = int(input()) - 1
	queue = [(0, S)]
	dist = [-1] * N
	while queue:
		(ndist, node) = heapq.heappop(queue)
		if dist[node] == -1:
			dist[node] = ndist
			for (neigh, cost) in g[node]:
				if dist[neigh] == -1:
					heapq.heappush(queue, (dist[node] + cost, neigh))
	print(' '.join((str(d) for (i, d) in enumerate(dist) if i != S)))
for _ in range(T):
	solve()


class node:

	def __init__(self):
		self.nodes = []
		self.nodeDist = []
		self.dist = -1

	def addNode(self, b, r):
		self.nodes.append(b)
		self.nodeDist.append(r)
for i in range(int(input())):
	[lNumb, edges] = list(map(int, input().split()))
	nodes = []
	for i in range(lNumb + 1):
		nodes.append(node())
	for j in range(edges):
		[a, b, r] = list(map(int, input().split()))
		nodes[a].addNode(nodes[b], r)
		nodes[b].addNode(nodes[a], r)
	firstNode = nodes[int(input())]
	firstNode.dist = 0
	checkNodes = [firstNode]
	while len(checkNodes):
		nextNodes = []
		for origNode in checkNodes:
			thisDist = origNode.dist
			for (checkIdx, nextNode) in enumerate(origNode.nodes):
				checkDist = nextNode.dist
				edgeDist = origNode.nodeDist[checkIdx]
				if checkDist == -1 or checkDist > thisDist + edgeDist:
					nextNode.dist = thisDist + edgeDist
					nextNodes.append(nextNode)
		checkNodes = nextNodes
	out = []
	for item in nodes[1:]:
		if item != firstNode:
			out.append(item.dist)
	print(' '.join(list(map(str, out))))


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


t = int(input())
for x in range(t):
	(n, m) = list(map(int, input().split(' ')))
	edges = [[] for y in range(n)]
	for y in range(m):
		(a, b, r) = list(map(int, input().split(' ')))
		edges[a - 1].append([b - 1, r])
		edges[b - 1].append([a - 1, r])
	s = int(input())
	length = [350 * n for y in range(n)]
	length[s - 1] = 0
	nodes = [y for y in range(n)]
	current = s - 1
	min_ = 0
	while len(nodes) > 0:
		nodes.remove(current)
		j = current
		for y in edges[current]:
			if length[current] + y[1] < length[y[0]]:
				length[y[0]] = length[current] + y[1]
		min_ = 350 * n
		for y in nodes:
			if length[y] < min_:
				min_ = length[y]
				j = y
		if j == current:
			break
		else:
			current = j
	for y in range(len(length)):
		if length[y] == 350 * n:
			length[y] = -1
	for y in length[:s - 1]:
		print(y, end=' ')
	for y in length[s:]:
		print(y, end=' ')
	print()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


import sys
import queue

class Vertex:

	def __init__(self):
		self.edges = {}

	def get_edges(self):
		return self.edges

	def add_edge(self, value, distance):
		if value not in self.edges or distance < self.edges[value]:
			self.edges[value] = distance

class Graph:

	def __init__(self, N):
		self.vertices = {}
		while N > 0:
			self.vertices[N] = Vertex()
			N -= 1

	def get_vertices(self):
		return self.vertices

	def get_vertex(self, value):
		return self.vertices[value]

	def add_vertex(self, value, vertex):
		self.vertices[value] = vertex

class Dijkstra:

	def __init__(self, graph):
		self.graph = graph

	def calculate(self, start):
		solved = {start: 0}
		adjacents = queue.PriorityQueue()
		self.update_adjacents(start, solved, adjacents)
		while not adjacents.empty():
			(distance, value) = adjacents.get()
			if value in solved:
				continue
			solved[value] = distance
			self.update_adjacents(value, solved, adjacents)
		return solved

	def update_adjacents(self, parent, solved, adjacents):
		edges = self.graph.get_vertex(parent).get_edges()
		for (value, distance) in edges.items():
			adjacents.put((solved[parent] + distance, value))

def read_integers():
	return [int(x) for x in sys.stdin.readline().split(' ')]

def build_graph(N, M):
	graph = Graph(N)
	while M > 0:
		(x, y, R) = read_integers()
		graph.get_vertex(x).add_edge(y, R)
		graph.get_vertex(y).add_edge(x, R)
		M -= 1
	return graph

def print_distances(distances, N, S):
	for i in range(1, N + 1):
		if i == S:
			continue
		distance = -1 if i not in distances else distances[i]
		print(distance, end=' ')
	print()

def execute_test_case():
	(N, M) = read_integers()
	graph = build_graph(N, M)
	dijkstra = Dijkstra(graph)
	S = int(sys.stdin.readline())
	distances = dijkstra.calculate(S)
	print_distances(distances, N, S)

def main():
	T = int(sys.stdin.readline())
	while T > 0:
		execute_test_case()
		T -= 1
main()


from heapq import heappush, heappop
import heapq
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	g = [[] for _ in range(N)]
	for _ in range(M):
		(x, y, r) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		g[x].append((r, y))
		g[y].append((r, x))
	S = int(input()) - 1
	paths = [-1] * N
	visited = [False] * N
	visited[S] = True
	cd = 0
	q = [(cd, S)]
	while q:
		(d, c) = heappop(q)
		for (r, n) in g[c]:
			nd = d + r
			if not visited[n]:
				visited[n] = True
				heappush(q, (nd, n))
				paths[n] = nd
			elif paths[n] > nd:
				index = q.index((paths[n], n))
				q[index] = (nd, n)
				heapq._siftdown(q, 0, index)
				paths[n] = nd
	paths = paths[:S] + paths[S + 1:]
	print(' '.join(map(str, paths)))


def mindist(dist, check):
	min2 = 100000
	for i in range(1, n + 1):
		if check[i] != 1 and dist[i] <= min2:
			min2 = dist[i]
			f = i
	return f
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = [] * (n + 1)
	list1 = {}
	weight = {}
	for j in range(n + 1):
		a.append([-1] * n)
		list1[j] = 0
		weight[j] = 100000
	for j in range(m):
		b = [] * 4
		b = list(map(int, input().split()))
		if a[b[0]][b[1] - 1] == -1 or a[b[0]][b[1] - 1] > b[2]:
			a[b[0]][b[1] - 1] = b[2]
		if a[b[1]][b[0] - 1] == -1 or a[b[1]][b[0] - 1] > b[2]:
			a[b[1]][b[0] - 1] = b[2]
	k1 = int(input())
	weight[k1] = 0
	for j in range(n - 1):
		u = mindist(weight, list1)
		list1[u] = 1
		for v in range(0, n):
			if list1[v + 1] != 1 and a[u][v] != -1 and (weight[u] != 100000) and (a[u][v] + weight[u] < weight[v + 1]):
				weight[v + 1] = a[u][v] + weight[u]
	for j in range(n):
		if weight[j + 1] != 0 and weight[j + 1] != 100000:
			print(weight[j + 1], end=' ')
		elif weight[j + 1] == 100000:
			print('-1', end=' ')
	print()


T = int(input().strip())
import heapq
for _ in range(T):
	(n, m) = map(int, input().strip().split())
	G = {}
	for _ in range(m):
		(i, j, w) = map(int, input().strip().split())
		i -= 1
		j -= 1
		if i in G:
			G[i][j] = min(w, G[i][j]) if j in G[i] else w
		else:
			G[i] = {j: w}
		if j in G:
			G[j][i] = min(w, G[j][i]) if i in G[j] else w
		else:
			G[j] = {i: w}
	s = int(input().strip()) - 1
	d = [float('inf') for _ in range(n)]
	q = [(0, s)]
	d[s] = 0
	while q:
		curr = heapq.heappop(q)
		for i in G[curr[1]]:
			x = d[curr[1]] + G[curr[1]][i]
			if d[i] > x:
				d[i] = x
				heapq.heappush(q, (d[i], i))
	print(' '.join(map(lambda x: str(x) if str(x) != 'inf' else str(-1), d[:s] + d[s + 1:])))


import queue
t = int(input())

class Node:

	def __init__(self, name):
		self.name = name
		self.distance = -1
		self.neighbors = {}

	def linkNode(self, n2, distance):
		if n2.name not in self.neighbors or (n2.name in self.neighbors and distance < self.neighbors[n2.name]):
			self.neighbors[n2.name] = distance
			n2.neighbors[self.name] = distance

	def __repr__(self):
		return self.__str__()

def handleTestCase():
	(n, m) = [int(item) for item in input().split(' ')]
	nodedict = {}
	for name in range(1, n + 1):
		node = Node(name)
		nodedict[name] = node
	for line in range(0, m):
		(x, y, r) = [int(item) for item in input().split(' ')]
		nodedict[x].linkNode(nodedict[y], r)
	start = int(input())
	startnode = nodedict[start]
	startnode.distance = 0
	visitqueue = queue.Queue()
	visitqueue.put(start)
	while not visitqueue.empty():
		current = visitqueue.get()
		currentnode = nodedict[current]
		currentdistance = currentnode.distance
		for neighbor in currentnode.neighbors:
			neighbornode = nodedict[neighbor]
			newneighbordistance = currentdistance + currentnode.neighbors[neighbor]
			if neighbornode.distance == -1 or newneighbordistance < neighbornode.distance:
				neighbornode.distance = newneighbordistance
				visitqueue.put(neighbor)
	outputlinelist = [str(nodedict[name].distance) for name in range(1, n + 1) if name != start]
	output = ' '.join(outputlinelist)
	print(output)
for testcase in range(0, t):
	handleTestCase()