Задачі
Самий довгий шлях в дереві
Самий довгий шлях в дереві
Дано неорієнтоване зважене дерево. Знайдіть у ньому найдовший шлях. Тобто знайдіть такі дві вершини, відстань між якими максимальна.
Вхідні дані
Перший рядок містить кількість вершин у дереві 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