eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Самий довгий шлях в дереві

Самий довгий шлях в дереві

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB

Дано неорієнтоване зважене дерево. Знайдіть у ньому найдовший шлях. Тобто знайдіть такі дві вершини, відстань між якими максимальна.

Вхідні дані

Перший рядок містить кількість вершин у дереві n\:(2 \le n \le 10^5). Наступні n - 1 рядок описують ребра. Кожен рядок містить три цілих числа: номери вершин, з'єднаних ребром (вершини пронумеровані числами від 1 до n), та вага ребра w\:(1 \le w \le 10^5).

Первая строка содержит количество вершин в дереве n\:(2 \le n \le 10^5). Следующие n - 1 строка описывают ребра. Каждая строка содержит три целых числа: номера вершин, соединенных ребром (вершины пронумерованы числами от 1 до n), и вес ребра w\:(1 \le w \le 10^5).

Вихідні дані

Виведіть довжину найдовшого шляху.

Приклад

Вхідні дані #1
6
1 2 3
2 3 4
2 6 2
6 4 6
6 5 5
Вихідні дані #1
12