Задача F. БОЛНИЦА

Селищата на един планински район, номерирани с числата от 1 до N, са свързани с M шосета така, че всеки две селища са свързани с не повече от едно шосе и от всяко селище може да се стигне до всяко друго селище по директно свързващото ги шосе или по път преминаващ през едно или повече други селища. За подобряване на здравното обслужване в района било решено да се построи нова болница, която да е разположена в някое от селищата или по свързващите ги шосета. За да се намали времето за достигане до болницата, когато това се налага по спешност, мястото трябва да бъде избрано така, че най-отдалеченото от болницата селище да е колкото може по-близо. Напишете програма F, която да определя мястото за строеж на новата болница.

Вход

На първия ред на стандартния вход ще бъде зададен броят T на тестовите примери, които програмата трябва да реши. Всеки тестов пример започва с ред, съдържащ числата N и M , разделени с един интервал (3 £ N £ 1001, 3 £ M £ 2900). Всеки от следващите M реда съдържа описанието на едно шосе – номерата I и J на селищата, които това шосе свързва и дължината D на шосето – положително дробно число, не надхвърлящо 100.

Изход

За всеки тестов пример програмата трябва да изведе на стандартния изход едно дробно число с четири цифри след десетичната точка – разстоянието от оптималното място за новата болница до най-отдалеченото от нея селище.

ПРИМЕР

Вход Изход

1 6.2500

5 6

3 1 8.5

3 2 2.0

2 5 6.1

4 5 4.4

4 1 6.6

5 1 2.45