Професор Флойд і професор Дейкстра ненавидят один одного. Після переїзду до Києва, вони вимагають надати їм кабінети в будівлях, максимально віддалених одна від одної.
Знайдіть цю відстань

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

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

Формат вхідних даних

В першому рядку два цілих числа \(N,M\) (\(1 \le N \le 100\) , \(0 \le M \le N*(N-1)/2\) ) - кількість вершин графа та кількість ребер відповідно.
В наступних \(M\) рядках міститься по 3 числа \(V1,V2,X\) , що позначають двосторонню дорогу між будівлями \(V1\) та \(V2\) довжиною \(X\) (\(1 \le V1,V2 \le N\) , \(0 \le X \le 100\))

Формат вихідних даних

Виведіть єдине число максимальну найкоротшу відстань між усіма парами будівель.

Приклад вхідних даних-1

3 2
1 2 1
2 3 2

Приклад вихідних даних-1

3

Приклад вхідних даних-2

3 0

Приклад вихідних даних-2

0