import sys input = lambda : sys.stdin.readline().rstrip() sys.setrecursionlimit(2*10**5+10) write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) # 木の読み込み・重みあり n = int(input()) ns = [[] for _ in range(n)] vs = [0]*n for _ in range(n-1): u,v,c = map(int, input().split()) ns[u].append((c,v)) ns[v].append((c,u)) """木におけるダブリングdouble 祖先と何かを同時に求める """ # 深さ def cdepth(ns, root=0): # rootを根としたときの深さ ps = [None] * n ps[root] = -1 q = [0] while q: u = q.pop() for c,v in ns[u]: if ps[v] is None: ps[v] = u vs[v] = c q.append(v) # psを元から持っている場合、引数のnsをpsにしてこの下だけで良い depth = [None] * len(ps) ns = [[] for _ in range(len(ps))] for i,p in enumerate(ps): ns[p].append(i) depth[root] = 0 q = [root] while q: u = q.pop() for v in ns[u]: if depth[v] is None: depth[v] = depth[u] + 1 q.append(v) return depth, ps # ダブリング def double(ps, vs=None): # global: n=psのサイズ prev = [[None]*n for _ in range(k)] # prev[i][j]: jから2^i個上の上司 vals = [[None]*n for _ in range(k)] # vals[i][j]: jから2^i個上の上司までの間の枝重みのmax for j in range(n): prev[0][j] = ps[j] vals[0][j] = vs[j] for i in range(1,k): for j in range(n): p = prev[i-1][j] if p>=0: prev[i][j] = prev[i-1][p] vals[i][j] = op(vals[i-1][j], vals[i-1][p]) else: prev[i][j] = p vals[i][j] = vals[i-1][j] return prev, vals # k: 必要桁数を定める必要アリ def cprev(u,i): """uからi個上の頂点を返す """ vv = ninf for j in range(k): if i>>j&1: vv = op(vv, vals[j][u]) u = prev[j][u] return u, vv # k: 必要桁数を定める必要アリ def lca(u,v): if depth[u]