ОПОРНІ ШКОЛИ#8300

ОПОРНІ ШКОЛИ

0,5 секунди

64 мегабайти

Дуже складна

В рамках процесу децентралізації постала задача створення опорних шкіл. В районі є $N$ селищ, деякі з яких з'єднані дорогами. Відомо, які саме селища з'єднані і відстані вздовж відповідних доріг. Потрібно забезпечити можливість доступу учнів усіх селищ району до опорної школи. При цьому, якщо існує декілька маршрутів до школи, то учні добиратимуться по найкоротшому з них. Визначте, в якому селищі потрібно розмістити школу так, щоб відстань від неї до найдальшого селища була мінімальною.

Вхідні дані

У першому рядку записані числа $N$ — кількість селищ ( $2 \leq N \leq 1000$ 2 \leq N \leq 1000), $M$ — кількість доріг, довжини яких відомі ( $2 \leq M \leq \frac{N \cdot ( N - 1 )}{2}$ 2 \leq M \leq \frac{N \cdot (N-1)}{2}).

У наступних $M$ рядках записана інформація про дороги — по $3$ числа (два цілих числа — номери селищ, які з'єднані дорогами, та одне додатне дійсне — довжина відповідної дороги).

Вихідні дані

У першому рядку виведіть номер селища, у якому потрібно розмістити опорну школу. Якщо є декілька варіантів розміщення школи, то виведіть номери селищ у порядку зростання.

У другому рядку виведіть відстань від школи до найдальшого селища з точністю до $2$ знаків.

Якщо задача не має розв'язку, то виведіть одне число -1.

Опорну школу варто розмістити у селищі № $2$ . Відстань від нього до інших складатиме:

до № $1$ — $5$ км,
до № $3$ — $2$ км,
до № $4$ — $5$ км.

Таким чином, найдальше селище розташоване на відстані $5$ км.

Приклади

Приклад 1