woogle.we#9417
Чи знаєте ви, що восени люди працюють краще? Це тому, що в давнину люди збирали врожай саме восени.
Темирулан вирішив відвідати офіси компанії Woogle. Деякі з цих офісів з'єднані двосторонніми шляхами, кожен з яких має певну вартість у волларах. Припустимо, що Темирулан має необмежену кількість волларів. Він оплачує кожен шлях за допомогою своєї картки Waspi. Зверніть увагу, що Темирулан може подорожувати між будь-якими парами офісів, і жоден шлях не є самозамкненим. Айдана хвилюється за Темирулана і хоче, щоб він витратив якомога менше грошей на цю подорож. Вона прагне встановити мінімально можливий ліміт на його картці (хто їх зрозуміє, цих дівчат?), щоб Темирулан не помітив різниці. Це означає, що якщо Темирулан подорожує з офісу в офіс найдешевшим шляхом (він завжди обирає оптимальний маршрут, звичка ACM), жоден платіж не буде відхилено через обмеження ліміту, для будь-якої пари офісів і .
Допоможіть Айдані визначити мінімальну кількість воларів, яку вона може встановити як ліміт на картці, щоб Темирулан міг оптимально дістатися з будь-якого офісу в будь-який інший.
Перший рядок містить два цілих числа , (2 \le n \le 100, 1 \le m \le n \cdot (n - 1) / 2) - кількість офісів і кількість доріг між ними.
Кожен з наступних рядків містить три невід'ємних цілих числа , , (1 \le v, u \le n, 1 \le w \le 10^5) - номери офісів і вартість шляху між ними.
Виведіть одне ціле число - мінімальний ліміт для картки Темирулана.
Приклад 1