Бензин

Між пунктами з номерами 1, 2, ..., N (N ≤ 150) прокладено декілька доріг. Довжина кожної дороги відома. По цій системі доріг можна дістатись з довільного згадуваного пункту у довільний інший. Автозаправки розміщено лише у пунктах. Потрібно визначити, яку максимальну відстань без заправки повинен бути у змозі проїзжати автомобіль, щоб, рухаючись по цій системі доріг, без проблем попадати з довільного пункту у довільний інший.

Вхідні дані

У першому рядку вхідного файлу знаходяться числа N і K (кількість доріг). У наступних K рядках вказано пари пунктів, з'єднаних дорогами та відстань між ними — ціле невід'ємне число кілометрів, яке не перевищує 10000. K ≤ 150^2.

Вихідні дані

У вихідному файлі повинно бути одне число — довжина максимального пробігу без дозаправки.

Приклади