Ghép cặp trên cây

Một khu dân cư gồm $2k$ ngôi nhà đánh số từ $1$ đến $2k$ và $2k-1$ con đường hai chiều. Con đường thứ $i$ nối hai nhà $a_i$ và $b_i$, đi qua nó mất $w_i$ đơn vị thời gian. Giữa hai ngôi nhà bất kỳ luôn có đúng một đường đi không lặp cạnh, nói cách khác hệ thống nhà và đường tạo thành một cây.

Có $k$ cặp bạn thân cần được xếp vào các ngôi nhà: mỗi người ở đúng một ngôi nhà và mỗi ngôi nhà có đúng một người. Với một cách xếp, gọi $f(i)$ là tổng thời gian đi trên đường đi ngắn nhất giữa hai ngôi nhà của cặp thứ $i$.

Hãy tính hai giá trị:

• $G$ — giá trị nhỏ nhất có thể của $f(1)+f(2)+\dots +f(k)$;
• $B$ — giá trị lớn nhất có thể của $f(1)+f(2)+\dots +f(k)$.

Hai giá trị này được tính độc lập với nhau: cách xếp đạt $G$ và cách xếp đạt $B$ không nhất thiết phải giống nhau.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $k$ — số cặp bạn thân.
  • $2k-1$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$, $w_i$ mô tả con đường thứ $i$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng hai số nguyên $G$ và $B$ cách nhau bởi một dấu cách.

Ràng buộc

• $1\le t\le 500$
• $1\le k\le {10}^5$
• $1\le a_i,b_i\le 2k$ và $a_i\ne b_i$
• $1\le w_i\le {10}^6$
• Các con đường trong mỗi bộ dữ liệu luôn tạo thành một cây.
• Tổng của $k$ trên tất cả các bộ dữ liệu trong một file không vượt quá $3·{10}^5$.

Ví dụ