Прекрасного сонячного дня Їжачок прогулювався своєю улюбленою полянкою. Проте, він побачив дещо незвичне, чого на полянці раніше не було. Це дещо здалеку здавалось схожим на клубок мотузок. Підійшовши ближче, розплутавши його та вивчивши матеріал, з якого він виготовлений, Їжачок прийшов до висновку, що це - бікфордів шнур.

Уважно подивившись на нього, Їжачок прийшов до висновку, що, схоже що, тому, хто його зробив, було скучно і у нього було багато вільного часу, так як шнур було заплутано, і на ньому було зав'язано величезну кількість вузлів! Після кропіткого перерахунку вияснилось, що усього є 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-та мотузка і за скільки секунд ця мотузка повністю згорить, якщо її підпалити з одного з кінців.

Кожну пару вузлів з'єднує максимум одна мотузка. Гарантується, що увесь шнур може згоріти, якщо підпалити довільни його вузол.

Вихідні дані

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