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: MEDIUM
Tags: Tree algorithms

Graph algorithms

Graph traversal

Starter code:

Solutions:
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))


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()


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))


def dfs(s=0, p=-1):
	global a
	global 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) = map(int, input().split())
	a[x] += [[y, z]]
	a[y] += [[x, z]]
print(dfs())


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))


from sys import stdin, stdout

def dfs(node):
	notVisited[node] = False
	cur = 0
	for (i, j) in enumerate(adj[node]):
		if notVisited[j[0]]:
			cur = max(cur, j[1] + dfs(j[0]))
	return cur
N = int(stdin.readline().strip())
adj = [[] for __ in range(N)]
notVisited = [True] * N
for __ in range(N - 1):
	(u, v, c) = map(int, stdin.readline().strip().split())
	adj[u].append((v, c))
	adj[v].append((u, c))
stdout.write(f'{dfs(0)}')


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))


import sys, queue
n = int(input())
e = [[] for _ in range(n + 1)]
for i in range(n - 1):
	(u, v, w) = list(map(int, input().split()))
	e[u].append((v, w))
	e[v].append((u, w))
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(max(dst))


from collections import deque
n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v, c) = 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))


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)


count = []

def DFs(d, node, visited, c):
	visited.add(node)
	for i in d[node]:
		if i[0] not in visited:
			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)
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))


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()


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))
main()


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
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) = map(int, input().strip().split(' '))
	graph[u][v] = c
	graph[v][u] = c
ans = solve(0, graph, visited)
print(ans)


n = int(input())
al = [[] for j in range(n)]
for i in range(n - 1):
	(a, b, c) = 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
	ca[n] = ca[n] + c
	for e in al[n]:
		p = e[0]
		q = e[1] + ca[n]
		if va[p] == 0:
			dfs(p, q)
dfs(0, 0)
print(max(ca))


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))


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:
		global ans
		ans = max(ans, cost)
		return
	for (v, c) in Adj[u]:
		if p == v:
			continue
		dfs(n, Adj, u, v, cost + c)
solve()


from collections import defaultdict
n = int(input())
visited = [0 for i in range(n + 1)]

def DFS(visited, graph, x):
	stack = [(x, 0)]
	count = 0
	max1 = float('-inf')
	while len(stack):
		flag = 0
		(temp, count) = stack.pop()
		visited[temp] = 1
		for i in graph[temp]:
			if visited[i[0]] == 0:
				flag = 1
				stack.append((i[0], count + i[1]))
				visited[i[0]] = 1
		if flag == 0:
			max1 = max(max1, count)
	return max1
graph = defaultdict(list)
for i in range(n - 1):
	(u, v, c) = map(int, input().split())
	graph[u].append((v, c))
	graph[v].append((u, c))
x = 0
print(DFS(visited, graph, x))


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)


from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from itertools import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from re import *
from os import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))
(graph, mod, szzz) = ({}, 10 ** 9 + 7, lambda : sorted(zzz()))

def getStr():
	return input()

def getInt():
	return int(input())

def listStr():
	return list(input())

def getStrs():
	return input().split()

def isInt(s):
	return '0' <= s[0] <= '9'

def input():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in input().split()]

def output(answer, end='\n'):
	stdout.write(str(answer) + end)

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
daysInMounth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
n = getInt()
for i in range(n):
	graph[i] = []
for i in range(n - 1):
	(x, y, z) = zzz()
	graph[x].append((y, z))
	graph[y].append((x, z))

def BSF(start):
	que = deque([start])
	dis = [float('-inf')] * (n + 1)
	dis[0] = 0
	vis = [0] * (n + 1)
	vis[0] = 1
	while que:
		x = que.pop()
		for nei in graph[x]:
			if vis[nei[0]]:
				continue
			newDis = nei[1] + dis[x]
			vis[nei[0]] = 1
			dis[nei[0]] = max(newDis, dis[nei[0]])
			que.append(nei[0])
	return dis
print(max(BSF(0)))


n = int(input())
d = {}
visited = [0] * n
dist = {}
for _ in range(n - 1):
	(u, v, c) = map(int, input().split())
	d.setdefault(u, []).append(v)
	d.setdefault(v, []).append(u)
	dist[min(u, v), max(u, v)] = c
stack = [[0, 0]]
ans = -1
while stack != []:
	temp = stack.pop()
	node = temp[0]
	distance = temp[1]
	visited[node] = 1
	for child in d[node]:
		if visited[child] == 0:
			stack.append([child, distance + dist[min(node, child), max(node, child)]])
	ans = max(ans, distance)
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()


def bfs(G, s):
	from queue import Queue
	n = len(G)
	Q = Queue()
	visited = [False] * n
	d = [0] * n
	d[s] = 0
	visited[s] = True
	Q.put(s)
	while not Q.empty():
		u = Q.get()
		for (v, weight) in G[u]:
			if not visited[v]:
				visited[v] = True
				d[v] = d[u] + weight
				Q.put(v)
	print(max(d))
n = int(input())
G = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v, c) = map(int, input().split())
	G[u].append((v, c))
	G[v].append((u, c))
bfs(G, 0)


n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
	(x, y, z) = 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))


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]
	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)


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)


import sys
readline = sys.stdin.readline

def i1():
	return int(readline())

def nl():
	return [int(s) for s in readline().split()]

def nn(n):
	return [int(readline()) for i in range(n)]

def nnp(n, x):
	return [int(readline()) + x for i in range(n)]

def nmp(n, x):
	return (int(readline()) + x for i in range(n))

def nlp(x):
	return [int(s) + x for s in readline().split()]

def nll(n):
	return [[int(s) for s in readline().split()] for i in range(n)]

def mll(n):
	return ([int(s) for s in readline().split()] for i in range(n))

def s1():
	return readline().rstrip()

def sl():
	return [s for s in readline().split()]

def sn(n):
	return [readline().rstrip() for i in range(n)]

def sm(n):
	return (readline().rstrip() for i in range(n))

def redir(s):
	global readline
	import os
	fn = sys.argv[0] + f'/../in-{s}.txt'
	readline = open(fn).readline if os.path.exists(fn) else readline
redir('j')
n = i1()
nodes = [[] for i in range(n + 1)]
costs = [[] for i in range(n + 1)]
seen = [False] * n
for i in range(n - 1):
	(u, v, c) = [int(i) for i in readline().split()]
	nodes[u].append(v)
	nodes[v].append(u)
	costs[u].append(c)
	costs[v].append(c)
stk = [[0, len(nodes[0])]]
seen[0] = True
ccc = [0] * n
while stk:
	top = stk[-1]
	r = top[0]
	idx = top[1] - 1
	ch = nodes[r]
	while idx >= 0 and seen[ch[idx]]:
		idx -= 1
	if idx < 0:
		stk.pop()
		continue
	top[-1] = idx
	c = ch[idx]
	seen[c] = True
	ccc[c] = ccc[r] + costs[r][idx]
	if nodes[c]:
		stk.append([c, len(nodes[c])])
print(max(ccc))


def dfs(u, cur):
	global 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)


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.buffer.readline())
Neo = lambda : list(map(int, sys.stdin.buffer.readline().split()))
n = I()
Ans = 0
G = defaultdict(list)
C = defaultdict(int)
for i in range(n - 1):
	(a, b, c) = Neo()
	G[a].append(b)
	G[b].append(a)
	C[a, b] = c
	C[b, a] = c

def hello(node, cost, vis):
	vis[node] = 1
	global Ans
	for i in G[node]:
		if not vis[i]:
			hello(i, cost + C[node, i], vis[:])
	else:
		Ans = max(Ans, cost)
vis = [0] * n
hello(0, 0, vis)
print(Ans)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()
import sys
input = sys.stdin.readline
scanner = lambda : int(input())
string = lambda : input().rstrip()
get_list = lambda : list(read())
read = lambda : map(int, input().split())
get_float = lambda : map(float, input().split())

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def is_integer(n):
	return math.ceil(n) == math.floor(n)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def next_prime(n, primes):
	while primes[n] != True:
		n += 1
	return n
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()

def binary_search(low, high, w, h, n):
	while low < high:
		mid = low + (high - low) // 2
		if check(mid, w, h, n):
			low = mid + 1
		else:
			high = mid
	return low

def check(moves, n):
	val = (moves + 1) // 2
	rem = moves - val
	sol = (val + 1) * (rem + 1)
	return sol < n

def sortSecond(val):
	return val[1]
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
alphs = 'abcdefghijklmnopqrstuvwxyz'
from itertools import permutations
import math
import bisect as bis
import random
import sys
import collections as collect
import functools as fnt

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

def solve():
	n = scanner()
	g = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v, c) = read()
		g[u].append((v, c))
		g[v].append((u, c))
	print(getmaxPath(g, 0, -1))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = 1
for i in range(t):
	solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	pass

def binary(n):
	return bin(n).replace('0b', '')

def decimal(s):
	return int(s, 2)

def pow2(n):
	p = 0
	while n > 1:
		n //= 2
		p += 1
	return p

def isPrime(n):
	if n == 1:
		return False
	else:
		root = int(n ** 0.5)
		root += 1
		for i in range(2, root):
			if n % i == 0:
				return False
		return True

def lts(l):
	s = ''.join(map(str, l))
	return s

def stl(s):
	l = list(s)
	return l

def sq(a, target, arr=[]):
	s = sum(arr)
	if s == target:
		return arr
	if s >= target:
		return
	for i in range(len(a)):
		n = a[i]
		remaining = a[i + 1:]
		ans = sq(remaining, target, arr + [n])
		if ans:
			return ans

def SieveOfEratosthenes(n):
	cnt = 0
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			cnt += 1
	return cnt

def nCr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
mod = int(1000000000.0) + 7
import math
n = int(input())
d = {}
visited = [0] * n
dist = {}
for _ in range(n - 1):
	(u, v, c) = map(int, input().split())
	d.setdefault(u, []).append(v)
	d.setdefault(v, []).append(u)
	dist[min(u, v), max(u, v)] = c
stack = [[0, 0]]
ans = -1
while stack != []:
	temp = stack.pop()
	node = temp[0]
	distance = temp[1]
	visited[node] = 1
	for child in d[node]:
		if visited[child] == 0:
			stack.append([child, distance + dist[min(node, child), max(node, child)]])
	ans = max(ans, distance)
print(ans)


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))
ilelec = lambda : map(int1, input().split())
alelec = lambda : list(map(int1, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
N = int(input())
G = defaultdict(list)
mark = {}

def addEdge(a, b, c):
	G[a].append(b)
	G[b].append(a)
	mark[a, b] = c
	mark[b, a] = c
Ans = 0

def dfs(node, par=-1, tot=0):
	global Ans
	Ans = max(Ans, tot)
	if len(G[node]) == 1 and node != 0:
		return 0
	c = 0
	for i in G[node]:
		if i != par:
			c = max(c, dfs(i, node, tot + mark[i, node]))
	Ans = max(Ans, c)
	return c
for i in range(N - 1):
	(a, b, c) = ilele()
	addEdge(a, b, c)
dfs(0)
print(Ans)


import os, sys
from io import BytesIO, IOBase

def main():
	n = rint()
	g = graph(n)
	for i in range(n - 1):
		(u, v, c) = rints()
		g.addEdge(u, v, c)
	g.dfsUtil(0)

class graph:

	def __init__(self, n):
		(self.gdict, self.n) = ([[] for _ in range(n)], n)

	def addEdge(self, node1, node2, w=None):
		self.gdict[node1].append((node2, w))
		self.gdict[node2].append((node1, w))

	def dfsUtil(self, v):
		(stack, self.visit, ans) = ([(v, 0)], [0] * self.n, 0)
		self.visit[v] = True
		while stack:
			(s, c) = stack.pop()
			for (i1, i2) in self.gdict[s]:
				if not self.visit[i1]:
					stack.append((i1, i2 + c))
					self.visit[i1] = True
					ans = max(ans, i2 + c)
		print(ans)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 8192
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
main()


def helper(curr, g, visited):
	ans = 0
	for i in g[curr]:
		if i[0] not in visited:
			visited.add(i[0])
			ans = max(ans, i[1] + helper(i[0], g, visited))
			visited.remove(i[0])
	return ans
n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(a, b, c) = [int(x) for x in input().split()]
	g[a].append([b, c])
	g[b].append([a, c])
visited = set()
visited.add(0)
print(helper(0, g, visited))


def find_heights(edges, node, par):
	ans = 0
	for (ch, cost) in edges.get(node, []):
		if ch != par:
			ans = max(ans, cost + find_heights(edges, ch, node))
	return ans

def main():
	from collections import defaultdict
	n = list(map(int, input().split()))
	n = n[0]
	edges = defaultdict(list)
	for _ in range(n - 1):
		(x, y, cost) = list(map(int, input().split()))
		edges[x].append((y, cost))
		edges[y].append((x, cost))
	ans = find_heights(edges, node=0, par=-1)
	print(ans)
import sys
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


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
	if parent != -1:
		e = '{} : {}'.format(parent, node)
		e1 = '{} : {}'.format(node, parent)
		if e in weights:
			dist += weights[e]
		else:
			dist += weights[e1]
		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)