Christmas is almost over, and so as one last activity, Elsa and Anna invite their ~T~ friends over to build gingerbread houses! Each person builds a community full of ~N~ gingerbread houses with ~N - 1~ trails, connecting each gingerbread house with another. Some trails may be longer than others, and so each gingerbread trail is given a distance, ~W~. It is guaranteed that every gingerbread house can be reached in a community from another gingerbread house.

Anna notices that some communities could be small and lonely, and so to expand the economy, she wants to connect all these communities together! Since the number of gingerbread materials are limited, she wants to know the minimum number of trails that need to be made, as well as which houses the trails will connect, so that the maximum distance between any two houses within all the communities is minimized. By giving this challenge to everyone, it will force everyone to compete over the best answer!

Elsa wants to solve this problem first, and so before Anna reveals any information, she asks you to create a program that will give her the answer! Will you help Elsa or get turned to ice?

Constraints

~(1 \le T \le 10)~

~(2 \le N \le 1000)~

~(1 \le W \le 10)~

All the houses in each community will have a unique integer representation.

Subtask 1 (50%)

~(1 \le T \le 2)~

~(2 \le N \le 10)~

~W = 1~.

Input Specification

The first line will contain integer ~T~.

For the next ~T~ communities, there will be 1 integer, ~N~, followed by ~N - 1~ lines.

Each of these ~N - 1~ lines will contain values ~a~, ~b~, and ~c~. This will result in a trail from house ~a~ to ~b~, with a distance of ~c~. This will be ~1~-indexed.

Output Specification

Print K, the minimum number of houses that need to be connected.

For the next K lines, print the house number which should form a trail to another house. The house number order should based on the order of the community it came from, so if the answer is house 3 in ~T_i~ and house 1 ~T_i + 1~, then you would print 3, followed by a 1 on the next line. If there are two answers for which house to pick, print the one with the smaller house number.

Sample Input

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

Sample Output

3
1
4
1

Explanation

In the first community, there should be a trail formed with house 1.

In the second community, there should be a trail formed with house 4.

In the third community, there should be a trail formed with house 1.