Welcome! Everything is fine.

You have arrived in The Medium Place, the place between The Good Place and The Bad Place. You are assigned a task that will either make people happier or torture them for eternity.

You have a list of k pairs of people who have arrived in a new inhabited neighborhood. You need to assign each of the 2k people into one of the 2k houses. Each person will be the resident of exactly one house, and each house will have exactly one resident.

Of course, in the neighborhood, it is possible to visit friends. There are 2k - 1 roads, each of which connects two houses. It takes some time to traverse a road. We will specify the amount of time it takes in the input. The neighborhood is designed in such a way that from anyone's house, there is exactly one sequence of distinct roads you can take to any other house. In other words, the graph with the houses as vertices and the roads as edges is a tree.

The truth is, these k pairs of people are actually soulmates. We index them from 1 to k. We denote by f(i) the amount of time it takes for the i-th pair of soulmates to go to each other's houses.

As we have said before, you will need to assign each of the 2k people into one of the 2k houses. You have two missions, one from the entities in The Good Place and one from the entities of The Bad Place. Here they are:

  * The first mission, from The Good Place, is to assign the people into the houses such that the sum of f(i) over all pairs i is minimized. Let's define this minimized sum as G. This makes sure that soulmates can easily and efficiently visit each other; 
  * The second mission, from The Bad Place, is to assign the people into the houses such that the sum of f(i) over all pairs i is maximized. Let's define this maximized sum as B. This makes sure that soulmates will have a difficult time to visit each other. 



What are the values of G and B?

Input

The first line of input contains a single integer t (1 ≤ t ≤ 500) denoting the number of test cases. The next lines contain descriptions of the test cases.

The first line of each test case contains a single integer k denoting the number of pairs of people (1 ≤ k ≤ 10^5). The next 2k - 1 lines describe the roads; the i-th of them contains three space-separated integers a_i, b_i, t_i which means that the i-th road connects the a_i-th and b_i-th houses with a road that takes t_i units of time to traverse (1 ≤ a_i, b_i ≤ 2k, a_i ≠ b_i, 1 ≤ t_i ≤ 10^6). It is guaranteed that the given roads define a tree structure.

It is guaranteed that the sum of the k in a single file is at most 3 ⋅ 10^5.

Output

For each test case, output a single line containing two space-separated integers G and B. 

Example

Input


2
3
1 2 3
3 2 4
2 4 3
4 5 6
5 6 5
2
1 2 1
1 3 2
1 4 3


Output


15 33
6 6

Note

For the sample test case, we have a minimum sum equal to G = 15. One way this can be achieved is with the following assignment:

  * The first pair of people get assigned to houses 5 and 6, giving us f(1) = 5; 
  * The second pair of people get assigned to houses 1 and 4, giving us f(2) = 6; 
  * The third pair of people get assigned to houses 3 and 2, giving us f(3) = 4. 



Note that the sum of the f(i) is 5 + 6 + 4 = 15. 

We also have a maximum sum equal to B = 33. One way this can be achieved is with the following assignment:

  * The first pair of people get assigned to houses 1 and 4, giving us f(1) = 6; 
  * The second pair of people get assigned to houses 6 and 2, giving us f(2) = 14; 
  * The third pair of people get assigned to houses 3 and 5, giving us f(3) = 13. 



Note that the sum of the f(i) is 6 + 14 + 13 = 33.

Difficulty: HARD
Tags: Tree algorithms

Graph algorithms

Graph traversal

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.buffer.readline
for T in range(int(input())):
	k = int(input())
	counts = [0] * (2 * k + 1)
	adjacencies = [list() for i in range(2 * k + 1)]
	for _ in range(2 * k - 1):
		(a, b, weight) = map(int, input().split())
		counts[a] += 1
		counts[b] += 1
		adjacencies[a].append((b, weight))
		adjacencies[b].append((a, weight))
	parents = [0] * (2 * k + 1)
	weights = [0] * (2 * k + 1)
	root = 1
	parents[root] = root
	queue = [0] * (2 * k)
	(head, tail) = (0, 0)
	queue[tail] = root
	tail += 1
	while head < tail:
		node = queue[head]
		for (child, weight) in adjacencies[node]:
			if parents[child] < 1:
				parents[child] = node
				weights[child] = weight
				queue[tail] = child
				tail += 1
		head += 1
	subtree_sizes = [1] * (2 * k + 1)
	maximum = minimum = 0
	index = len(queue) - 1
	while index >= 0:
		node = queue[index]
		subtree_sizes[parents[node]] += subtree_sizes[node]
		if subtree_sizes[node] & 1:
			minimum += weights[node]
		maximum += weights[node] * min(subtree_sizes[node], 2 * k - subtree_sizes[node])
		index -= 1
	print(minimum, maximum)


import sys
reader = (map(int, line.split()) for line in sys.stdin)

def minmaxPairs(g, costDict, n):
	G = B = 0
	s = 1
	stack = [s]
	traversal = []
	visited = [False] * (n + 1)
	subtreeSize = [1 for _ in range(n + 1)]
	while stack:
		v = stack.pop()
		if not visited[v]:
			visited[v] = True
			for to in g[v]:
				if not visited[to]:
					stack.append(v)
					stack.append(to)
		else:
			to = traversal[-1]
			if (v, to) in costDict:
				cost = costDict[v, to]
			else:
				cost = costDict[to, v]
			toSize = subtreeSize[to]
			subtreeSize[v] += toSize
			minComp = min(toSize, n - toSize)
			G += minComp % 2 * cost
			B += minComp * cost
		traversal.append(v)
	return (G, B)
(t,) = next(reader)
for _ in range(t):
	(k,) = next(reader)
	n = 2 * k
	g = [[] for i in range(n + 1)]
	costDict = {}
	for i in range(n - 1):
		(v, to, cost) = next(reader)
		costDict[v, to] = cost
		g[v].append(to)
		g[to].append(v)
	(G, B) = minmaxPairs(g, costDict, n)
	print(G, B)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
for T in range(int(input())):
	k = int(input())
	counts = [0] * (2 * k + 1)
	adjacencies = [list() for i in range(2 * k + 1)]
	for _ in range(2 * k - 1):
		(a, b, weight) = map(int, input().split())
		counts[a] += 1
		counts[b] += 1
		adjacencies[a].append((b, weight))
		adjacencies[b].append((a, weight))
	parents = [0] * (2 * k + 1)
	weights = [0] * (2 * k + 1)
	root = 1
	parents[root] = root
	queue = [root]
	index = 0
	while index < len(queue):
		node = queue[index]
		for (child, weight) in adjacencies[node]:
			if parents[child] < 1:
				parents[child] = node
				weights[child] = weight
				queue.append(child)
		index += 1
	subtree_sizes = [1] * (2 * k + 1)
	maximum = minimum = 0
	for node in reversed(queue):
		subtree_sizes[parents[node]] += subtree_sizes[node]
		if subtree_sizes[node] & 1:
			minimum += weights[node]
		maximum += weights[node] * min(subtree_sizes[node], 2 * k - subtree_sizes[node])
	print(minimum, maximum)


import sys

def input():
	return sys.stdin.readline().strip()

def solve():
	k = int(input())
	n = 2 * k
	e = [[] for i in range(n)]
	p = [None] * n
	for i in range(n - 1):
		(a, b, t) = map(int, input().split())
		a -= 1
		b -= 1
		e[a].append((b, t))
		e[b].append((a, t))
	q = [0]
	qi = 0
	while qi < len(q):
		x = q[qi]
		qi += 1
		px = p[x]
		for (v, w) in e[x]:
			if v != px:
				q.append(v)
				p[v] = x
	d1 = [False] * n
	d2 = [0] * n
	m = 0
	M = 0
	for qi in range(len(q) - 1, -1, -1):
		x = q[qi]
		px = p[x]
		cnt = 1
		c1 = 1
		for (v, w) in e[x]:
			if v != px:
				if d1[v]:
					m += w
					cnt += 1
				dv = d2[v]
				M += w * min(dv, n - dv)
				c1 += dv
		d1[x] = cnt % 2
		d2[x] = c1
	print(m, M)
for i in range(int(input())):
	solve()


def main():
	import sys
	input = sys.stdin.buffer.readline
	t = int(input())
	for _ in range(t):
		K = int(input())
		N = 2 * K
		adj = [[] for _ in range(N + 1)]
		edge = []
		for _ in range(N - 1):
			(a, b, t) = map(int, input().split())
			adj[a].append((b, t))
			adj[b].append((a, t))
		st = [1]
		seen = [0] * (N + 1)
		seen[1] = 1
		par_t = [0] * (N + 1)
		child = [[] for _ in range(N + 1)]
		seq = []
		while st:
			v = st.pop()
			seq.append(v)
			for (u, t) in adj[v]:
				if not seen[u]:
					seen[u] = 1
					st.append(u)
					par_t[u] = t
					child[v].append(u)
		seq.reverse()
		G = B = 0
		dp = [1] * (N + 1)
		for v in seq:
			for u in child[v]:
				dp[v] += dp[u]
			m = min(dp[v], N - dp[v])
			G += par_t[v] * (m % 2)
			B += par_t[v] * m
		print(G, B)
main()


import os, sys
from io import BytesIO, IOBase

def main():
	for _ in range(int(input())):
		n = 2 * int(input())
		path = [[] for _ in range(n)]
		cost = [[] for _ in range(n)]
		for _ in range(n - 1):
			(a1, b1, c) = map(int, input().split())
			path[a1 - 1].append(b1 - 1)
			path[b1 - 1].append(a1 - 1)
			cost[a1 - 1].append(float(c))
			cost[b1 - 1].append(float(c))
		(st, poi, visi) = ([0], [0] * n, [1] + [0] * (n - 1))
		(child, pt, G, B) = ([1] * n, 0, 0, 0)
		while len(st):
			(x, y) = (st[-1], path[st[-1]])
			if poi[x] != len(y) and visi[y[poi[x]]]:
				poi[x] += 1
			if poi[x] == len(y):
				st.pop()
				if len(st):
					child[st[-1]] += child[x]
					z = cost[st[-1]][poi[st[-1]] - 1]
					pt -= z
					if child[x] & 1:
						G += z
			else:
				(i, j) = (y[poi[x]], cost[x][poi[x]])
				st.append(i)
				pt += j
				B += pt
				poi[x] += 1
				visi[i] = 1
		(st, poi, visi, x, diff) = ([0], [0] * n, [1] + [0] * (n - 1), 0, 0)
		while 1:
			(co, maxi, su, which) = (-1, 0, 1, -1)
			for (ind, j) in enumerate(path[x]):
				if visi[j]:
					continue
				visi[j] = 1
				su += child[j]
				if child[j] > maxi:
					(maxi, which) = (child[j], j)
					co = cost[x][ind]
			if maxi - diff <= su - maxi:
				break
			B -= co * (2 * maxi - su - diff)
			diff += su - maxi
			x = which
		print(int(G), int(B))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
t = int(input())
for _ in range(t):
	k = int(input())
	line = [[] for _ in range(2 * k)]
	deg = [0] * (2 * k)
	ll = []
	for (u, v, c) in (map(int, sys.stdin.readline().split()) for _ in range(2 * k - 1)):
		line[u - 1].append((v - 1, c))
		line[v - 1].append((u - 1, c))
		deg[u - 1] += 1
		deg[v - 1] += 1
		ll.append((u - 1, v - 1, c))
	N = 2 * k
	(G, B) = (0, 0)
	stack = [v for v in range(1, 2 * k) if deg[v] == 1]
	sub_size = [0] * (2 * k)
	while stack:
		v = stack.pop()
		sub_size[v] += 1
		deg[v] -= 1
		for (dest, cost) in line[v]:
			if dest > 0 and deg[dest] < 2:
				continue
			deg[dest] -= 1
			sub_size[dest] += sub_size[v]
			if (N - sub_size[v]) % 2 or sub_size[v] % 2:
				G += cost
			B += cost * min(N - sub_size[v], sub_size[v])
			if dest > 0 and deg[dest] == 1:
				stack.append(dest)
	print(G, B)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def dfs(graph, alpha):
	n = len(graph)
	visited = [False] * n
	finished = [False] * n
	parents = [-1] * n
	stack = [alpha]
	dp = [0] * n
	while stack:
		v = stack[-1]
		if not visited[v]:
			visited[v] = True
			for u in graph[v]:
				if parents[u] == -1:
					parents[u] = v
				if not visited[u]:
					stack.append(u)
		else:
			stack.pop()
			dp[v] += 1
			for u in graph[v]:
				if finished[u]:
					dp[v] += dp[u]
			finished[v] = True
	return (visited, dp, parents)
for _ in range(int(input()) if True else 1):
	n = int(input())
	n *= 2
	graph = [[] for i in range(n + 1)]
	edges = {}
	for i in range(n - 1):
		(x, y, k) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
		edges[x, y] = edges[y, x] = k
	(visited, dp, parents) = dfs(graph, 1)
	(mi, ma) = (0, 0)
	for i in range(2, n + 1):
		mi += dp[i] % 2 * edges[i, parents[i]]
		ma += min(dp[i], n - dp[i]) * edges[i, parents[i]]
	print(mi, ma)


from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		k = int(input())
		adj = [[] for __ in range(2 * k + 1)]
		for __ in range(2 * k - 1):
			(u, v, w) = readIntArr()
			adj[u].append([v, w])
			adj[v].append([u, w])
		g = [0]
		b = [0]

		@bootstrap
		def dfs(node, p):
			cnts = 1
			for (child, w) in adj[node]:
				if child == p:
					continue
				cnt2 = (yield dfs(child, node))
				if cnt2 % 2 == 1:
					g[0] += w
				b[0] += min(cnt2, k * 2 - cnt2) * w
				cnts += cnt2
			yield cnts
		dfs(1, -1)
		allans.append([g[0], b[0]])
	multiLineArrayOfArraysPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultVal, dimensionArr):
	dv = defaultVal
	da = dimensionArr
	if len(da) == 1:
		return [dv for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
	print('? {} {}'.format(x, y))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

def main():
	for _ in range(N()):
		k = N()
		n = 2 * k
		gp = defaultdict(dict)
		for _ in range(n - 1):
			(f, t, c) = RL()
			gp[f][t] = c
			gp[t][f] = c
		vis = [0] * (n + 1)
		vis[1] = 1
		q = [(1, 1)]
		par = [-1] * (n + 1)
		dp = [1] * (n + 1)
		mi = ma = 0
		while q:
			(nd, st) = q.pop()
			if st:
				q.append((nd, 0))
				for nex in gp[nd]:
					if vis[nex] == 1:
						continue
					vis[nex] = 1
					q.append((nex, 1))
					par[nex] = nd
			else:
				if nd == 1:
					continue
				dp[par[nd]] += dp[nd]
				mpar = min(dp[nd], n - dp[nd])
				mi += gp[par[nd]][nd] if mpar % 2 == 1 else 0
				ma += gp[par[nd]][nd] * mpar
		print(mi, ma)
main()


from sys import stdin, stdout

def getminmaxsum(k, dic):
	res = [0, 0]
	hs = set()
	kt = 2 * k
	st = []
	resst = []
	depth = 0
	b = [1, 0, depth]
	st.append(b)
	while len(st) > 0:
		cur = st[-1]
		hs.add(cur[0])
		hasnext = False
		for nn in dic[cur[0]]:
			if nn[0] not in hs:
				hasnext = True
				next = [nn[0], nn[1], cur[2] + 1]
				st.append(next)
		if not hasnext:
			cnt = 1
			st.pop()
			while len(resst) > 0 and cur[2] < resst[-1][0]:
				resdepth = resst.pop()
				cnt += resdepth[1]
			resst.append([cur[2], cnt])
			if cnt % 2 == 1:
				res[0] += cur[1]
			res[1] += cur[1] * min(cnt, kt - cnt)
	return res

def dfs(node, dic, hs, res, kt, ew):
	hs.add(node)
	if node not in dic:
		return 1
	cnt = 1
	for nn in dic[node]:
		if nn[0] not in hs:
			cnt += dfs(nn[0], dic, hs, res, kt, nn[1])
	if cnt % 2 == 1:
		res[0] += ew
	res[1] += ew * min(cnt, kt - cnt)
	return cnt
t = int(stdin.readline())
for i in range(t):
	k = int(stdin.readline())
	dic = {}
	for j in range(2 * k - 1):
		abt = list(map(int, stdin.readline().split()))
		a = abt[0]
		b = abt[1]
		t = abt[2]
		ra = [a, t]
		rb = [b, t]
		if not dic.__contains__(a):
			dic[a] = []
		if not dic.__contains__(b):
			dic[b] = []
		dic[a].append(rb)
		dic[b].append(ra)
	res = getminmaxsum(k, dic)
	stdout.write(str(res[0]) + ' ' + str(res[1]) + '\n')