SUPPORT SCHOOLS
As part of the decentralization process, the task of establishing hub schools has emerged. There are N villages in the district, some of which are connected by roads. The connections between villages and the distances along these roads are known. It is essential to ensure that students from all villages in the district can reach the hub school. If multiple routes to the school exist, students will choose the shortest one. Your task is to determine in which village the school should be located so that the distance to the farthest village is minimized.
Input Data:
The first line contains two numbers: N - the number of villages (2 ≤ N ≤ 1000), and M - the number of roads with known lengths (2 ≤ M ≤ N(N-1)/2)*.
The next M lines provide information about the roads, each containing three numbers: two integers representing the villages connected by the road, and one positive real number indicating the length of that road.
Output Data:
On the first line, output the number of the village where the hub school should be located. If there are multiple suitable villages, list their numbers in ascending order.
On the second line, output the distance from the school to the farthest village, rounded to 2 decimal places. If the problem has no solution, output the number -1.
For example, the hub school should be placed in village No. 2. The distances from it to other villages are:
to No. 1 - 5 km,
to No. 3 - 2 km,
to No. 4 - 5 km.
Thus, the farthest village is located at a distance of 5 km.