human
Give me a Python code to find the diameter of the tree given the following:
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
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to find the diameter of the tree.

import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

sys.setrecursionlimit(100001)

class Edge:
    def __init__(self,arg_to,arg_dist):
        self.to = arg_to
        self.dist = arg_dist

V = int(input())
G = [[] for _ in range(V)]

for _ in range(V-1):
    from_,to_,dist_ = map(int,input().split())
    G[from_].append(Edge(to_,dist_))
    G[to_].append(Edge(from_,dist_))

ans = 0

def recursive(node_id,parent):
    max_path1 = 0
    max_path2 = 0

    global ans

    for edge in G[node_id]:
        if edge.to == parent:
            continue
        tmp_dist = edge.dist+recursive(edge.to,node_id)
        if tmp_dist > max_path1:
            max_path2 = max_path1
            max_path1 = tmp_dist
        elif tmp_dist > max_path2:
            max_path2 = tmp_dist

    ans = max(ans,max_path1+max_path2)
    return max_path1

recursive(V//2,-1)
print("%d"%(ans))