In the highland, people live in towns. There are roads between pairs of towns, so that all the towns are connected by paths. Because the roads are different in length and surface, each road has a constant traveling time.

Now, the government wants to build two hospitals in two of these towns. Which two towns should be chosen to locate the two hospitals?

Let t_i denotes the time town i travel to its nearer hospital by a path costing the shortest time. The time traveling through a path is the sum of traveling time of each road on the path. The time traveling inside towns is omitted.

The principle for locating the two hospitals is that the maximum t_i must be minimized. If there are multi roads between two towns, only the lowest cost road will be considered. There may exists roads from one town to itself, but in our scene, these roads are useless.

Now, given the roads and their traveling time, it is your job to find the two towns to build the two hospitals. Fortunately, in our cases, the solution of the problem is unique.

The first line of input is an integer k, which is the number of cases. The following 2k lines contain k cases.

In each case, the first line contains two integers N and E, which are the number of towns and the number of roads in this case. All the towns in the case are labeled as 1, 2, ..., N. (2 <= N <= 500, N-1 <= E <= 2000). The second line contains 3E integers, that is a list as u₁, v₁, w₁, ..., u_E, v_E, w_E. u_i and v_i denotes the two relating towns of the i-th road without direction, and w_i is the cost time of the road.

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

1 2