Heidi's friend Jenny is asking Heidi to deliver an important letter to one of their common friends. Since Jenny is Irish, Heidi thinks that this might be a prank. More precisely, she suspects that the message she is asked to deliver states: "Send the fool further!", and upon reading it the recipient will ask Heidi to deliver the same message to yet another friend (that the recipient has in common with Heidi), and so on.

Heidi believes that her friends want to avoid awkward situations, so she will not be made to visit the same person (including Jenny) twice. She also knows how much it costs to travel between any two of her friends who know each other. She wants to know: what is the maximal amount of money she will waste on travel if it really is a prank?

Heidi's n friends are labeled 0 through n - 1, and their network of connections forms a tree. In other words, every two of her friends a, b know each other, possibly indirectly (there is a sequence of friends starting from a and ending on b and such that each two consecutive friends in the sequence know each other directly), and there are exactly n - 1 pairs of friends who know each other directly.

Jenny is given the number 0.


-----Input-----

The first line of the input contains the number of friends n (3 ≤ n ≤ 100). The next n - 1 lines each contain three space-separated integers u, v and c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 10^4), meaning that u and v are friends (know each other directly) and the cost for travelling between u and v is c.

It is guaranteed that the social network of the input forms a tree.


-----Output-----

Output a single integer – the maximum sum of costs.


-----Examples-----
Input
4
0 1 4
0 2 2
2 3 3

Output
5

Input
6
1 2 3
0 2 100
1 4 2
0 3 7
3 5 10

Output
105

Input
11
1 0 1664
2 0 881
3 2 4670
4 2 1555
5 1 1870
6 2 1265
7 2 288
8 7 2266
9 2 1536
10 6 3378

Output
5551



-----Note-----

In the second example, the worst-case scenario goes like this: Jenny sends Heidi to the friend labeled by number 2 (incurring a cost of 100), then friend 2 sends her to friend 1 (costing Heidi 3), and finally friend 1 relays her to friend 4 (incurring an additional cost of 2).

Difficulty: interview

Starter code:

Solutions:
import sys

sys.setrecursionlimit(10**6)

ans = 0

def solve():
    n = int(input())
    Adj = [[] for i in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, sys.stdin.readline().split())
        Adj[ai].append((bi, ci))
        Adj[bi].append((ai, ci))

    dfs(n, Adj, -1, 0, 0)

    print(ans)

def dfs(n, Adj, p, u, cost):
    if u != 0 and len(Adj[u]) == 1:
        nonlocal ans
        ans = max(ans, cost)
        return

    for (v, c) in Adj[u]:
        if p == v:
            continue
        dfs(n, Adj, u, v, cost + c)

def __starting_point():
    solve()
__starting_point()

n = int(input())
cnx = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, c = [int(i) for i in input().split()]
    cnx[u].append([v, c])
    cnx[v].append([u, c])

def cost(cur, src = -1):
    ans = 0
    for v, c in cnx[cur]:
        if v == src: continue
        ans = max(ans, c + cost(v, cur))
    return ans

ans = cost(0)
print(ans)



def dfs(s = 0, p = -1):
    nonlocal a
    nonlocal n
    if len(a[s]) == 1 and p != -1:
        return a[s][0][1]
    o = -1
    pp = -1
    for i in range(len(a[s])):
        if a[s][i][0] != p:
            if o == -1:
                o = dfs(a[s][i][0], s)
            else:
                o = max(o, dfs(a[s][i][0], s))
        else:
            pp = i
    if p != -1:
        return o + a[s][pp][1]
    return o

n = int(input())
a = [[] for i in range(n)]
for i in range(n-1):
    x, y, z = list(map(int, input().split()))
    a[x] += [[y, z]]
    a[y] += [[x, z]]
print(dfs())



def dfs(u,cur):
    nonlocal ans
    vis[u]=True
    flag=True
    for x in vec[u] :
        v=x[0]
        c=x[1]
        if not vis[v] :
            dfs(v,cur+c)
            flag=False
    if flag:
        ans=max(cur,ans)
ans=0
vec=[]
vis=[]
i=0
n=int(input())
while(i<n) :
    vec.append([])
    vis.append(False)
    i+=1
i=1
while(i<n):
    u,v,c=(int(x) for x in input().split(' '))
    vec[u].append((v,c))
    vec[v].append((u,c))
    i+=1
dfs(0,0)
print(ans)


n = int(input())
matrix = [[] for i in range(n)]
for i in range(n - 1):
    a = list(map(int, input().split()))
    matrix[a[0]].append([a[1], a[2]])
    matrix[a[1]].append([a[0], a[2]])
way = [float('inf') for i in range(n)]
used = [False for i in range(n)]
v = 0
way[0] = 0
for i in range(n):
    used[v] = True
    for j in matrix[v]:
        way[j[0]] = min(way[j[0]], way[v] + j[1])
    m = float('inf')
    for j in range(n):
        if way[j] < m and not used[j]:
            m = way[j]
            v = j
print(max(way))

import sys, queue

n = int(input())
e = [[] for _ in range(n+1)]
#print(e)
for i in range(n-1):
	u, v, w = list(map(int, input().split()))
	e[u].append((v,w))
	e[v].append((u,w))
	
#print(e)

volt = [False for _ in range(n+1)]
dst = [0 for i in range(n+1)]

q = queue.Queue()

q.put(0)

while (not q.empty()):
	curr = q.get()
	volt[curr] = True
	for nb in e[curr]:
		if (not volt[nb[0]]):
			dst[nb[0]] = dst[curr] + nb[1]
			q.put(nb[0])
			volt[nb[0]] = True

#print(dst)
print(max(dst))




def getmaxpath(g, v, par):
    maxp = 0
    for u, c in g[v]:
        if u == par:
            continue
        maxp = max(maxp, c + getmaxpath(g, u, v))
    return maxp

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n-1):
    u, v, c = (int(x) for x in input().split())
    g[u].append((v,c,))
    g[v].append((u,c,))
print(getmaxpath(g, 0, -1))
    


def dfs(d,di):
    stack = [[0,0]]
    mark = {i:False for i in range(n)}
    mark[0]=True
    res=[]
    while stack:
        s = stack.pop()
        x,cost=s[0],s[1]
        res.append(cost)
        for i,y in enumerate(d[x]):
            if mark[y]==False:
                if di.get((x,y))==None:
                    new_cost=di[(y,x)]
                else:new_cost=di[(x,y)]
                stack.append([y,cost+new_cost])
                mark[y]=True
    print(max(res))
n = int(input())
di,d={},{}
for i in range(n-1):
    u,v,c = map(int,input().split())
    di[(u,v)]=c
    if d.get(u)==None:d[u]=[]
    if d.get(v)==None:d[v]=[]
    d[u].append(v)
    d[v].append(u)
dfs(d,di)

count=[]

def DFs(d,node,visited,c):
    visited.add(node)
    for i in d[node]:
        if i[0] not in visited:
            #c=c+i[1]
            DFs(d,i[0],visited,c+i[1])
    count.append(c)
    
            
def dfs(d,n):
    visited=set()
    
    for i in d.keys():
        if i not in visited:
            c=0
            DFs(d,i,visited,c)
            #count.append(a)


n=int(input())
d={}
for i in range(n):
    d[i]=[]
for i in range(n-1):
    u,v,c=map(int,input().split(' '))
    d[u].append([v,c])
    d[v].append([u,c])

dfs(d,n)
print(max(count))

from collections import deque
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v, c = list(map(int, input().split()))
    adj[u].append((v, c))
    adj[v].append((u, c))
dist = [10**9] * n
dist[0] = 0
q = deque()
q.append((0, n))
while q:
    i, p = q.popleft()
    for i2, c in adj[i]:
        if i2 == p:
            continue
        dist[i2] = dist[i] + c
        q.append((i2, i))
print(max(dist))


import sys
mod = 1000000007
def get_array(): return list(map(int, sys.stdin.readline().split()))
def get_ints(): return map(int, sys.stdin.readline().split())
def input(): return sys.stdin.readline()
def print_array(a): print(" ".join(map(str, a)))
def maxCost(cost, tree, c, p):
    frnds = tree[c]
    if len(frnds) == 1 and frnds[0] == p: return 0
    l = []
    for frnd in frnds:
        if frnd != p: l.append(cost[c][frnd] + maxCost(cost, tree, frnd, c))
    return max(l)
def main():
    n = int(input())
    cost = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    tree = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v, c = get_ints()
        tree[u].append(v)
        tree[v].append(u)
        cost[u][v] = cost[v][u] = c
    print(maxCost(cost, tree, 0, 0))
            
def __starting_point():
    main()
__starting_point()

n = int(input())
 
tree = {}
for i in range(n-1):
    _from, _to, cost = map(int, input().split())
    if _from not in tree:
        tree[_from] = [(_to,cost)]
    else:
        tree[_from].append((_to,cost))
    if _to not in tree:
        tree[_to] = [(_from,cost)]
    else:
        tree[_to].append((_from,cost))
 
passed = [0]*n
all_cost = []
def compute_cost(node, cost):
    passed[node] = 1
    if len(tree[node])!=0:
        for subnode in tree[node]:
            if passed[subnode[0]] != 1:
                all_cost.append(cost+subnode[1])
                compute_cost(subnode[0], cost+subnode[1])
 
compute_cost(0,0)
print (max(all_cost))

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
  x, y, z = list(map(int, input().split()))
  g[x] += (y, z),
  g[y] += (x, z),


def go(x, f):
  ret = 0
  for y, z in g[x]:
    if y != f:
      ret = max(ret, z + go(y, x))
  return ret


print(go(0, -1))


# maa chudaaye duniya
from collections import defaultdict
graph = defaultdict(list)
n = int(input())
weights = {}
for _ in range(n-1):
	a, b, w = map(int, input().split())
	edge1 = '{} : {}'.format(a, b)
	edge2 = '{} : {}'.format(b, a)
	graph[a].append(b)
	graph[b].append(a)
	weights[edge1] = w
	weights[edge2] = w

maxsf = [-10**9]
visited = [False for i in range(n+1)]

def dfs(node, parent, dist):
	visited[node] = True
	# print(maxsf)
	# print('checking ', node, parent)
	# print(visited)
	if parent != -1:
		e ='{} : {}'.format(parent, node)
		e1 = '{} : {}'.format(node, parent)
		if e in weights:
			dist += weights[e]
			# print(e, dist)
		else:
			dist += weights[e1]
			# print(e1, dist)
		if dist > maxsf[0]:
			maxsf[0] = dist
	for children in graph[node]:
		if not visited[children]:
			dfs(children, node, dist)
	
dfs(0, -1, 0)
print(*maxsf)

from collections import defaultdict

graph = defaultdict(list)
d = {}
n = int(input())
for i in range(n-1):
    u,v,cost = list(map(int,input().split()))
    graph[u].append(v)
    graph[v].append(u)
    x = str(u)+':'+str(v)
    y = str(v)+':'+str(u)
    d[x] = cost
    d[y] = cost

q = [[0,0]]
ans = []
visited = [False for i in range(n)]
visited[0] = True
while q!=[]:
    node,cost = q[0][0],q[0][1]
    q.pop(0)
    leaf = True
    for v in graph[node]:
        if visited[v]==False:
            visited[v]=True
            leaf = False
            x = str(node)+':'+str(v)
            y = str(v)+':'+str(node)
            if x in d:
                c = d[x]
            else:
                c = d[y]
            q.append([v,cost+c])
    if leaf:
        ans.append(cost)
print(max(ans))

n = int(input())
li = [[] for i in range(0,n)]
for i in range(n-1):
    u, v, c = map(int,input().split())
    li[u].append((v,c))
    li[v].append((u,c))

mc = 0
cost = 0
visited = [False] * n
def DFS(num,visited,cost):
    nonlocal mc
    if cost > mc:
        mc = cost
    visited[num] = True
    for i in range(len(li[num])):
        if not visited[li[num][i][0]]:
            DFS(li[num][i][0],visited,cost+li[num][i][1])
DFS(0,visited,0)
print(mc)

n=int(input())
al=[[] for j in range(n)]
for i in range(n-1):
        a,b,c=list(map(int,input().split()))
        al[a].append([b,c])
        al[b].append([a,c])

mc=0
va=[0]*(n)
ca=[0]*(n)
def dfs(n,c):
        va[n]=1
        #print(c)
        ca[n]=ca[n]+c

        for e in al[n]:
                #print(e)
                p=e[0]
                q=e[1]+ca[n]
                if(va[p]==0):
                        dfs(p,q)
        
        
dfs(0,0)
print(max(ca))

'''
mc = 0
cost = 0
visited = [False] * n
def DFS(num,visited,cost):
    nonlocal mc
    if cost > mc:
        mc = cost
    visited[num] = True
    for i in range(len(li[num])):
        if not visited[li[num][i][0]]:
            DFS(li[num][i][0],visited,cost+li[num][i][1])
DFS(0,visited,0)
print(mc)'''


n = int(input())
dicts = {}
for i in range(n - 1):
    temparr = input()
    temparr = temparr.split()
    u = int(temparr[0])
    v = int(temparr[1])
    weight = int(temparr[2])

    if u not in dicts:
        dicts[u] = []
    dicts[u].append((v, weight))

    if v not in dicts:
        dicts[v] = []
    dicts[v].append((u, weight))
maxans = 0 

def dfs(cur, par = -1, sums = 0):
    nonlocal dicts
    nonlocal maxans
    for element in dicts[cur]:
        nextelement = element[0]
        nextweight = element[1]
        if par != nextelement:
            sums+=nextweight
            if maxans <= sums:
                maxans = sums 
            dfs(nextelement , cur, sums)
            sums-=nextweight
dfs(0,-1, 0)
print(maxans)
print()

# void dfs(int cur , int par = -1)
# {
#   // do what u want
#   for(auto x : g[cur])
#   {
#     if(x!=par)
#     {
#       dfs(x,cur);
#     }
#   }
# }

#print(dicts)






cost = 0
def solve(u, graph, visited):
  nonlocal cost
  visited[u] = True
  visited[u] = True
  cost = 0
  explore = -1
  subcost = 0
  current = 0
  for v in graph[u]:
    if not visited[v] and graph[u][v] > subcost:
      current = max(current, solve(v, graph, visited) + graph[u][v])
  return max(current, cost)

def __starting_point():
  N = int(input().strip())
  graph = {x: {} for x in range(N)}
  visited = [False for _ in range(N + 1)]
  for i in range(N - 1):
    u,v,c = list(map(int, input().strip().split(" ")))
    graph[u][v] = c
    graph[v][u] = c
  ans = solve(0, graph, visited)
  print(ans)


__starting_point()

def solve(u, graph, visited):
  visited[u] = True
  current = 0
  for v in graph[u]:
    if not visited[v]:
      current = max(current, solve(v, graph, visited) + graph[u][v])
  return current

def __starting_point():
  N = int(input().strip())
  graph = {x: {} for x in range(N)}
  visited = [False for _ in range(N + 1)]
  for i in range(N - 1):
    u,v,c = list(map(int, input().strip().split(" ")))
    graph[u][v] = c
    graph[v][u] = c
  ans = solve(0, graph, visited)
  print(ans)


__starting_point()

n=int(input())
d={}
cost=[]
for i in range(n):
    cost.append(n*[0])
for i in range(n-1):
    u,v,c=list(map(int,input().split()))
    if u not in d:
        d[u]=[]
    if v not in d:
        d[v]=[]
    d[u].append(v)
    d[v].append(u)
    cost[u][v]=c
    cost[v][u]=c
khoroch=n*[0]
visit=n*[0]
def dfs(d,s,parent):
    nonlocal ans
    visit[s]=1
    khoroch[s]=cost[parent][s]+khoroch[parent]
    #print(s,visit[s])
    ans=max(khoroch[s],ans)
    for x in d[s]:
        if(visit[x]==0):
            dfs(d,x,s)
ans=0
dfs(d,0,0)
print(ans)
    



import sys
import threading
from collections import defaultdict



adj=defaultdict(list)
n=int(input())
for _ in range(n-1):
    x,y,b=list(map(int,input().split()))
    adj[x].append((y,b))
    adj[y].append((x,b))
def fun(node,par,x):
    y=x
    for ch,b in adj[node]:
        if ch!=par:
            y=max(fun(ch,node,x+b),y)
    return y


def main():
    print(fun(0,-1,0))
                  
def __starting_point():
    sys.setrecursionlimit(10**6)
    threading.stack_size(10**8)
    t = threading.Thread(target=main)
    t.start()
    t.join() 
__starting_point()

# Author: S Mahesh Raju
# Username: maheshraju2020
# Created on: 25/09/2020 01:47:42

from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda: int(stdin.readline().strip())
is1 = lambda: stdin.readline().strip()
iia = lambda: list(map(int, stdin.readline().strip().split()))
isa = lambda: stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

def getAns(d):
    queue = [[0, 0]]
    seen = set()
    res = float("-inf")
    while len(queue):
        cur, cost = queue.pop()
        if cur not in seen:
            seen.add(cur)
            res = max(res, cost)
            for a, b in d.get(cur, []):
                queue.append([a, b + cost])
    return res


n = ii1()
d = {}
for i in range(n - 1):
    a, b, cost = iia()
    d.setdefault(a, []).append([b, cost])
    d.setdefault(b, []).append([a, cost])
print(getAns(d))