题目背景

树的进阶

题目描述

给定一棵树，树中每条边都有一个正整数权值，求该树的直径。

输入格式

第一行为一个正整数n,表示这棵树有n个节点。 接下来n−1行， 每行三个正整数u,v,w，表示u,v(u,v≤n) 有一条权值为w的边相连， 数据保证没有重边或自环。

输出格式

一个整数表示树的直径。

样例

7 
1 2 3 
2 4 2
2 5 1
1 3 4
3 6 2
3 7 3

12

3
1 2 42
2 3 46

88

数据范围

2≤n≤100000,1≤w≤100;