Столовая

Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.

Помогите найти такое здание!

Входные данные

В первой строке входного файла INPUT.TXT находятся два целых числа N и M – количество зданий и количество дорог, соединяющих здания (1 ≤ N ≤ 100, 0 ≤ M ≤ N×(N−1)/2). Далее в M строках расположены описания дорог: 3 целых числа s_i, e_i, l_i – здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1 ≤ s_i, e_i ≤ N, 0 ≤ l_i ≤ 100, дороги двунаправленные). Гарантируется, что между любыми двумя зданиями существует путь.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – номер искомого здания. Если есть несколько зданий удовлетворяющих поставленным критериям, выберите среди них здание с наименьшим номером.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!