woogle.we
Знаете ли Вы, что осенью люди работают лучше? Просто потому, что древние собирали урожай каждую осень.
Темирулан решил путешествовать по офисам Woogle. Между некоторыми офисами есть несколько двусторонних путей. Каждый из этих путей стоит некоторого количества волларов. Можно предположить, что Темирулан имеет неограниченное количество волларов. Темирулан оплачивает путь, используя свою карту Waspi. Обратите внимание, что Темирулан может путешествовать между всеми парами офисов, и там нет самозамкнутых путей. Айдана беспокоится о Темирулане. Она хочет, чтобы Темирулан потратил меньше денег на это путешествие. Она хочет установить минимально возможный лимит на его карту (кто понимает этих девушек?) так, чтобы Темирулан не увидел разницу. Это означает, что если Темирлан идет из офиса A в офис B самым дешевым способом (он всегда идет оптимальным образом, привычка ACM), то никакой его платеж во время путешествия не будет отклонен из-за ограничения лимита, для любого офиса A и B.
Помогите Айдане выбрать минимальное количество воларов, которые она может установить на своей карточке в качестве лимита, и в то же время чтобы Темирулан смог оптимально добраться из любого офиса в любой офис.
Входные данные
Первая строка содержит два целых числа n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ n * (n - 1) / 2) - количество офисов и дорог между ними.
Каждая из следующих m строк содержит три неотрицательных целых числа v, u, w (1 ≤ v, u ≤ n, 1 ≤ w ≤ 10^5) - номера офисов и стоимость пути.
Выходные данные
Выведите одно целое число - минимальный лимит для карты Темирулана.