[Login|Register]
Problems

Status

Rank

Problem 1123
Two Hospitals
Time Limit: 2000ms
Memory Limit: 65536kb
Description

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 ti 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 ti 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.

Input

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 u1, v1, w1, ..., uE, vE, wE. ui and vi denotes the two relating towns of the i-th road without direction, and wi is the cost time of the road.

Output
For case, output the labels of the two towns in one line, with the smaller label in front.
Sample Input
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
Sample Output
1 2
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).