Central Hub Selection

You are given an undirected weighted graph representing N cities and M roads. Each road connects two different cities and has a positive length. Your task is to choose a city as the hub such that the maximum shortest distance from that hub to any other city is minimized. In other words, for each city, compute the shortest paths to all other cities using Dijkstra's algorithm and then select the city for which the longest of these shortest paths is as small as possible. If there are ties, choose the city with the smallest index.

Input: The first line contains two integers N and M. The next M lines each contain three integers u, v, and l where u and v are the cities connected by a road and l is the length of that road.

Output: Output two space-separated integers: the 1-indexed number of the chosen hub city and the minimized maximum distance from that hub to any other city.

The problem can be mathematically expressed as follows:

\[ \min_{1 \leq i \leq N} \; \max_{1 \leq j \leq N} \; d(i,j), \]

where \(d(i,j)\) is the shortest distance between city \(i\) and city \(j\).

inputFormat

The input contains multiple lines. The first line has two integers N and M separated by a space. Each of the following M lines contains three integers u, v, and l, representing a bidirectional road between cities u and v with length l.

outputFormat

Print two space-separated integers: the index of the chosen hub city (1-indexed) and the minimized maximum shortest distance from this hub to all other cities.## sample

4 5
1 2 5
1 3 10
2 3 2
2 4 3
3 4 1

2 5