C. Jeremy Bearimy
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Добро пожаловать! Все хорошо.

Вы прибыли в Среднее место, место между Хорошим местом и Плохим местом. Вам поручено выполнить два задания, одно сделает всех людей счастливыми, другое будет мучить их вечно.

У вас есть список $$$k$$$ пар людей, которые прибыли в новый район. Вам нужно назначить каждому из $$$2k$$$ людей свой из $$$2k$$$ домов. Каждый человек будет владельцем ровно одного дома и каждый дом будет иметь ровно одного владельца.

Конечно, в этом районе можно перемещаться между домами. Всего есть $$$2k - 1$$$ дорога, каждая из них соединяет два дома. Требуется некоторое время, чтобы проехать по дороге. Эти времена известны для каждой дороги. Район спроектирован таким образом, что между любыми двумя домами существует ровно один путь по дорогам от одного дома до другого, не проходящий по одной и той же дороге дважды. Другими словами, граф, в котором вершины это дома, а ребра это дороги это дерево.

Люди в каждой из $$$k$$$ пар людей хорошо дружат и любят ходить в гости. Мы пронумеруем пары людей от $$$1$$$ до $$$k$$$. Обозначим за $$$f(i)$$$ время, которое требуется $$$i$$$-й паре людей, чтобы проехать между домами друг друга.

Как уже было сказано ранее, вы должны сопоставить каждому из $$$2k$$$ людей один из $$$2k$$$ домов. У вас есть две миссии, одна назначена из Хорошего места, другая назначена из Плохого места. Эти миссии заключаются в следующем:

  • Первая миссия, из Хорошего места, заключается в том, чтобы сопоставить людям дома, так чтобы сумма $$$f(i)$$$ по всем парам $$$i$$$ была минимальна. Давайте обозначим эту минимальную возможную сумму за $$$G$$$. Это дает нам уверенность, что все пары друзей могут легко и эффективно посещать друг друга;
  • Вторая миссия, из Плохого места, заключается в том, чтобы сопоставить людям дома, так чтобы сумма $$$f(i)$$$ по всем парам $$$i$$$ была максимальна. Давайте обозначим эту максимальную возможную сумму за $$$B$$$. Это дает нам уверенность, что все пары друзей могут только трудно и неэффективно посещать друг друга;

Чему равны значения $$$G$$$ и $$$B$$$?

Входные данные

В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 500$$$), количество тестовых случаев. В следующих строках находится описание тестовых случаев.

Первая строка каждого тестового случая содержит единственное целое число $$$k$$$, обозначающая количество пар людей ($$$1 \le k \le 10^5$$$). В следующих $$$2k - 1$$$ строках находится описание дорог; в $$$i$$$-й строке находится три целых числа $$$a_i, b_i, t_i$$$, которые обозначают, что $$$i$$$-я дорога соединяет дома $$$a_i$$$ и $$$b_i$$$ и требует $$$t_i$$$ единиц времени, чтобы проехать по ней ($$$1 \le a_i, b_i \le 2k$$$, $$$a_i \neq b_i$$$, $$$1 \le t_i \le 10^6$$$). Гарантируется, что данные дороги образуют структуру дерева.

Гарантируется, что сумма всех $$$k$$$ по всем тестовым случаям не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого тестового случая, выведите два целых числа $$$G$$$ и $$$B$$$, разделенные пробелом.

Пример
Входные данные
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
Выходные данные
15 33
6 6
Примечание

Для первого тестового случая, мы можем получить минимальную сумму равную $$$G = 15$$$. Один из способов достичь такую сумму это следующее назначение домов:

  • Первой паре людей назначим дома $$$5$$$ и $$$6$$$, что даст нам $$$f(1) = 5$$$;
  • Второй паре людей назначим дома $$$1$$$ и $$$4$$$, что даст нам $$$f(2) = 6$$$;
  • Третьей паре людей назначим дома $$$3$$$ и $$$2$$$, что даст нам $$$f(3) = 4$$$.

Обратите внимание, что тогда сумма всех $$$f(i)$$$ это $$$5 + 6 + 4 = 15$$$.

Также мы можем получить максимальную сумму равной $$$B = 33$$$. Один из способов достичь такую сумму это следующее назначение домов:

  • Первой паре людей назначим дома $$$1$$$ и $$$4$$$, что даст нам $$$f(1) = 6$$$;
  • Второй паре людей назначим дома $$$6$$$ и $$$2$$$, что даст нам $$$f(2) = 14$$$;
  • Третьей паре людей назначим дома $$$3$$$ и $$$5$$$, что даст нам $$$f(3) = 13$$$.

Обратите внимание, что тогда сумма всех $$$f(i)$$$ это $$$6 + 14 + 13 = 33$$$.