EduBrick

Диаметр взвешенного дерева

1000 мс · 256 МБ · всё или ничего

Найдите наибольшую длину пути в дереве со взвешенными рёбрами.

Формат ввода

В первой строке - число вершин nn (1≤n≤1051 \le n \le 10^5).

В следующих n−1n-1 строках - тройки vv, uu, ww: ребро веса ww (0≤w≤1090 \le w \le 10^9).

Формат вывода

Выведите длину наибольшего пути.

Примеры

ввод
4
1 2 3
2 3 4
3 4 5
вывод
12
ввод
3
1 2 1000000000
1 3 1000000000
вывод
2000000000
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.