After completing her final semester, Savita is back home. She is excited to meet all her friends. Her $N$ friends live in different houses spread across the city.    

There are $\mbox{M}$ roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same pair of houses. Savita and Friends decide to meet.  

Savita wants to choose a point(not necessarily an integer) $P$ on the road numbered $K$, such that, the maximum of $dist(i)$ for all $1\leq i\leq N$ is minimised, 

where $dist(i)$ is the shortest distance between the ${i^{'th}$ friend and $P$.    

If K'th road connects friend $A$ and friend $B$ you should print distance of chosen point from $A$. Also, print the $max(dist(i))$ for all $1\leq i\leq N$. If there is more than one solution, print the one in which the point $P$ is closest to $A$.     

Note: 

Use scanf/printf instead of cin/cout. Large input files.
Order of $A$ and $B$ as given in the input must be maintained. If P is at a distance of 8 from $A$ and 2 from $B$, you should print 8 and not 2.  

Input Format

First line contain $T$, the number of testcases. 

T testcases follow. 

First Line of each testcase contains 3 space separated integers $N,M,K$ . 

Next $\mbox{M}$ lines contain description of the $i^{th}$ road : three space separated integers $A,B,C$, where $\mbox{C}$ is the length of road connecting $A$ and $B$.      

Constraints

$1\leq T\leq10$ 

$2\leq N,M\leq10^5$ 

$N-1\leq M\leq N*(N-1)/2$ 

$1\leq A,B\leq N$ 

$1\leq C\leq10^9$ 

$1\leq K\leq M$    

Output Format

For each testcase, print two space separated values in one line. The first value is the distance of $P$ from the point $A$ and the second value is the maximum of all the possible shortest paths between $P$ and all of Savita's and her friends' houses. Round both answers to $5$ decimal digits and print exactly $5$ digits after the decimal point.   

Sample Input
2
2 1 1
1 2 10
4 4 1
1 2 10
2 3 10
3 4 1
4 1 5

Sample Output
5.00000 5.00000
2.00000 8.00000

Explanation

First testcase: 

As $K$ = 1, they will meet at the point $P$ on the road that connects friend $1$ with friend $2$. If we choose mid point then distance for both of them will be $5$. In any other position the maximum of distance will be more than $5$.

Second testcase: 

As $K$ = 1, they will meet at a point $P$ on the road connecting friend $1$ and friend $2$. If we choose point at a distance of $2$ from friend $\mbox{I}$:
Friend $1$ will have to travel distance $2$. 

Friend $2$ will have to travel distance $8$. 

Friend $3$ will have to travel distance $8$. 

Friend $4$ will have to travel distance $7$. 

So, the maximum will be $8$. 

In any other position of point choosen, the maximum distance will be more than $8$.   

Timelimits

Timelimits for this problem is 2 times the environment limit.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import os
import sys
import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import os
import sys
import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import os
import sys
import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import heapq as heap

def get_distanceAB(toB, A):
	delta = [-1] * len(toB)
	curr = [(0, A)]
	while curr:
		(d, i) = heap.heappop(curr)
		if delta[i] >= 0:
			continue
		delta[i] = d
		for (j, e) in toB[i]:
			if delta[j] < 0:
				heap.heappush(curr, (d + e, j))
	return delta
M = int(input())
for t in range(M):
	(N, M, K) = map(int, input().split())
	edges = []
	toB = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		toB[A].append((B, C))
		toB[B].append((A, C))
	(A, B, C) = edges[K - 1]
	dxA = get_distanceAB(toB, A)
	dxB = get_distanceAB(toB, B)
	maxs = []
	for i in range(1, N + 1):
		x = (C + dxB[i] - dxA[i]) / 2
		maxs.append((x, dxA[i] + x))
	maxs.sort()
	points = []
	for (x, toB) in maxs:
		while points:
			(x0, y0) = points[-1]
			if y0 > toB - x + x0:
				break
			points.pop()
		if points:
			(x0, y0) = points[-1]
			xy = x0 + y0
			if toB > xy - x:
				x1 = (xy - toB + x) / 2
				points.append((x1, xy - x1))
				points.append((x, toB))
		else:
			if x > 0:
				points.append((0, toB - x))
			points.append((x, toB))
	(x, toB) = points[-1]
	if x < C:
		points.append((C, toB + x - C))
	(Xmin, Ymin) = points[0]
	for (x, toB) in points:
		if toB < Ymin:
			Xmin = x
			Ymin = toB
	print('%.5f %.5f' % (Xmin, Ymin))


import os
import sys
import heapq as heap

def get_distanceAB(toB, A):
	delta = [-1] * len(toB)
	curr = [(0, A)]
	while curr:
		(d, i) = heap.heappop(curr)
		if delta[i] >= 0:
			continue
		delta[i] = d
		for (j, e) in toB[i]:
			if delta[j] < 0:
				heap.heappush(curr, (d + e, j))
	return delta
M = int(input())
for t in range(M):
	(N, M, K) = map(int, input().split())
	edges = []
	toB = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		toB[A].append((B, C))
		toB[B].append((A, C))
	(A, B, C) = edges[K - 1]
	dxA = get_distanceAB(toB, A)
	dxB = get_distanceAB(toB, B)
	maxs = []
	for i in range(1, N + 1):
		x = (C + dxB[i] - dxA[i]) / 2
		maxs.append((x, dxA[i] + x))
	maxs.sort()
	points = []
	for (x, toB) in maxs:
		while points:
			(x0, y0) = points[-1]
			if y0 > toB - x + x0:
				break
			points.pop()
		if points:
			(x0, y0) = points[-1]
			xy = x0 + y0
			if toB > xy - x:
				x1 = (xy - toB + x) / 2
				points.append((x1, xy - x1))
				points.append((x, toB))
		else:
			if x > 0:
				points.append((0, toB - x))
			points.append((x, toB))
	(x, toB) = points[-1]
	if x < C:
		points.append((C, toB + x - C))
	(Xmin, Ymin) = points[0]
	for (x, toB) in points:
		if toB < Ymin:
			Xmin = x
			Ymin = toB
	print('%.5f %.5f' % (Xmin, Ymin))


import heapq as heap

def get_distanceAB(toB, A):
	delta = [-1] * len(toB)
	curr = [(0, A)]
	while curr:
		(d, i) = heap.heappop(curr)
		if delta[i] >= 0:
			continue
		delta[i] = d
		for (j, e) in toB[i]:
			if delta[j] < 0:
				heap.heappush(curr, (d + e, j))
	return delta
M = int(input())
for t in range(M):
	(N, M, K) = map(int, input().split())
	edges = []
	toB = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		toB[A].append((B, C))
		toB[B].append((A, C))
	(A, B, C) = edges[K - 1]
	dxA = get_distanceAB(toB, A)
	dxB = get_distanceAB(toB, B)
	maxs = []
	for i in range(1, N + 1):
		x = (C + dxB[i] - dxA[i]) / 2
		maxs.append((x, dxA[i] + x))
	maxs.sort()
	points = []
	for (x, toB) in maxs:
		while points:
			(x0, y0) = points[-1]
			if y0 > toB - x + x0:
				break
			points.pop()
		if points:
			(x0, y0) = points[-1]
			xy = x0 + y0
			if toB > xy - x:
				x1 = (xy - toB + x) / 2
				points.append((x1, xy - x1))
				points.append((x, toB))
		else:
			if x > 0:
				points.append((0, toB - x))
			points.append((x, toB))
	(x, toB) = points[-1]
	if x < C:
		points.append((C, toB + x - C))
	(Xmin, Ymin) = points[0]
	for (x, toB) in points:
		if toB < Ymin:
			Xmin = x
			Ymin = toB
	print('%.5f %.5f' % (Xmin, Ymin))


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def porter(ends, roots, infor):
	kmo = [-1 for _ in ends]
	pritority = []
	enc = []
	heappush(pritority, (0, roots))
	while pritority:
		(weight, actual) = heappop(pritority)
		if infor in ends[actual][1]:
			continue
		ends[actual][1][infor] = weight
		kmo[actual] = weight
		enc.append(actual)
		for (neighbor, length) in ends[actual][0]:
			if not infor in ends[neighbor][1]:
				heappush(pritority, (weight + length, neighbor))
	return (enc, kmo)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	ends = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		ends[a][0].append((b, c))
		ends[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = porter(ends, a, 'A')
	(historyB, distancesB) = porter(ends, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def rop():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
rop()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


import math
import os
import random
import re
import sys
from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


import math
import os
import random
import re
import sys
from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


import heapq

def calc_dist(G, start):
	dist = [-1] * len(G)
	active = [(0, start)]
	while active:
		(d, i) = heapq.heappop(active)
		if dist[i] >= 0:
			continue
		dist[i] = d
		for (j, e) in G[i]:
			if dist[j] < 0:
				heapq.heappush(active, (d + e, j))
	return dist
T = int(input())
for t in range(T):
	(N, M, K) = map(int, input().split())
	edges = []
	G = [[] for i in range(N + 1)]
	for i in range(M):
		(A, B, C) = map(int, input().split())
		edges.append((A, B, C))
		G[A].append((B, C))
		G[B].append((A, C))
	(A, B, C) = edges[K - 1]
	distA = calc_dist(G, A)
	distB = calc_dist(G, B)
	peaks = []
	for i in range(1, N + 1):
		x = (C + distB[i] - distA[i]) / 2
		peaks.append((x, distA[i] + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	(xmin, ymin) = pts[0]
	for (x, y) in pts:
		if y < ymin:
			xmin = x
			ymin = y
	print('%.5f %.5f' % (xmin, ymin))


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()


from heapq import heapify, heappush, heappop
from math import inf

def full_dijkstra(nodes, source, type_tag):
	out = [-1 for _ in nodes]
	p_queue = []
	visit_history = []
	heappush(p_queue, (0, source))
	while p_queue:
		(weight, actual) = heappop(p_queue)
		if type_tag in nodes[actual][1]:
			continue
		nodes[actual][1][type_tag] = weight
		out[actual] = weight
		visit_history.append(actual)
		for (neighbor, length) in nodes[actual][0]:
			if not type_tag in nodes[neighbor][1]:
				heappush(p_queue, (weight + length, neighbor))
	return (visit_history, out)
lista = []
lista2 = []
lista3 = []
lista4 = []
lista5 = []

def run(n, m, k, edges):
	nodes = [([], {}) for _ in range(n + 1)]
	for (a, b, c) in edges:
		nodes[a][0].append((b, c))
		nodes[b][0].append((a, c))
	(a, b, k_dis) = edges[k - 1]
	lista5.append(k_dis)
	(historyA, distancesA) = full_dijkstra(nodes, a, 'A')
	(historyB, distancesB) = full_dijkstra(nodes, b, 'B')
	pairs = list(zip(distancesA, distancesB))[1:]
	distB = distancesB
	distA = distancesA
	peaks = []
	C = k_dis
	N = n
	for (da, db) in zip(distA[1:], distB[1:]):
		point_delta = db - da
		x = (k_dis + point_delta) / 2
		peaks.append((x, da + x))
	peaks.sort()
	pts = []
	for (x, y) in peaks:
		while pts:
			(x0, y0) = pts[-1]
			if y0 > y - x + x0:
				break
			pts.pop()
		if pts:
			(x0, y0) = pts[-1]
			xy = x0 + y0
			if y > xy - x:
				x1 = (xy - y + x) / 2
				pts.append((x1, xy - x1))
				pts.append((x, y))
		else:
			if x > 0:
				pts.append((0, y - x))
			pts.append((x, y))
	(x, y) = pts[-1]
	if x < C:
		pts.append((C, y + x - C))
	print('%.5f %.5f' % min(pts, key=lambda x: x[1]))

def official_run():
	t = int(input())
	for i in range(t):
		(n, m, k) = map(int, input().split(' '))
		edges = [tuple(map(int, input().split(' '))) for _ in range(m)]
		run(n, m, k, edges)
official_run()