В прекрасный солнечный день Ёжик прогуливался по своей любимой полянке. Однако, он увидел нечто необычное, чего на полянке раньше не было. Это нечто издали казалось похожим на клубок верёвок. Однако, подойдя поближе, распутав его и изучив материал, из которого он изготовлен, Ёжик пришёл к выводу, что это - бикфордов шнур.

Внимательно посмотрев на него, Ёжик пришёл к выводу, что, похоже что, тому, кто его сделал, было скучно и у него было много свободного времени, так как шнур был запутан, и на нём было завязано огромное количество узлов! После кропотливого пересчёта, выяснилось, что всего имеется n узлов и m соединений между узлами. Каждое из них соединяет два узла и горит равномерно. При поджигании узла загораются все соединения, которые его содержат.

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

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

Первая строка содержит два целых числа n и m (2 ≤ n ≤ 100, 1 ≤ m ≤ n · (n - 1) / 2) - количество узлов и веревок между узлами, соответственно.

Следующие m строк содержат описания соединений между узлами - три целых числа ai, bi и ti (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ ti ≤ 1000) - номера узлов, которые соединяет i-ая веревка и за сколько секунд эта веревка полностью сгорит, будучи подожжённой с одного из концов.

Каждую пару узлов соединяет максимум одна веревка. Гарантируется, что весь шнур может сгореть, если поджечь любой его узел.

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

Выведите пару чисел - номер узла, который надо поджечь, и за какое время при этом сгорит весь шнур.