Diameter of a Tree




Given a tree T with non-negative weight, find the diameter of the tree.

The diameter of a tree is the maximum distance between two nodes in a tree.

Constraints

* 1 ≤ n ≤ 100,000
* 0 ≤ wi ≤ 1,000

Input


n
s1 t1 w1
s2 t2 w2
:
sn-1 tn-1 wn-1


The first line consists of an integer n which represents the number of nodes in the tree. Every node has a unique ID from 0 to n-1 respectively.

In the following n-1 lines, edges of the tree are given. si and ti represent end-points of the i-th edge (undirected) and wi represents the weight (distance) of the i-th edge.

Output

Print the diameter of the tree in a line.

Examples

Input

4
0 1 2
1 2 1
1 3 3


Output

5


Input

4
0 1 1
1 2 2
2 3 4


Output

7
#include <bits/stdc++.h>
#define INF 999999999
 
using namespace std;
 
typedef pair<int,int>P;
 
const int MAX_N = 100000;
vector<P> G[MAX_N];
int d[MAX_N]; 
bool visited[MAX_N];
 
void dfs(int v)
{
    visited[v] = true;
    for(int i=0; i<G[v].size(); i++){
        if(!visited[G[v][i].first]){
            d[G[v][i].first] = d[v] + G[v][i].second;
            dfs(G[v][i].first);
        }
    }
}
 
int main()
{
    int n,max0=0,maxd,maxx=0;
    scanf("%d",&n);
    fill(d,d+n,INF);
    fill(visited,visited+n,false);
    for(int i=1; i<n; i++){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
        G[y].push_back(make_pair(x,z));
    }
    d[0] = 0;
    dfs(0);
    for(int i=0; i<n; i++){
        if(max0 < d[i]){
            max0 = d[i];
            maxd = i;
        }
    }
    fill(d,d+n,INF);
    fill(visited,visited+n,false);
    d[maxd] = 0;
    dfs(maxd);
    for(int i=0; i<n; i++){
        maxx = max(maxx,d[i]);
    }
    cout << maxx << "\n";
}
