Problem:


Score : 1100 points

Problem Statement

There is a tree with N vertices, numbered 1 through N.
The i-th edge in this tree connects Vertices A_i and B_i and has a length of C_i.

Joisino created a complete graph with N vertices.
The length of the edge connecting Vertices u and v in this graph, is equal to the shortest distance between Vertices u and v in the tree above.

Joisino would like to know the length of the longest Hamiltonian path (see Notes) in this complete graph.
Find the length of that path.

Notes

A Hamiltonian path in a graph is a path in the graph that visits each vertex exactly once.

Constraints

2 \leq N \leq 10^5

1 \leq A_i < B_i \leq N

The given graph is a tree.

1 \leq C_i \leq 10^8

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{N-1} B_{N-1} C_{N-1}

Output

Print the length of the longest Hamiltonian path in the complete graph created by Joisino.

Sample Input 1

5
1 2 5
3 4 7
2 3 3
2 5 2

Sample Output 1

38

The length of the Hamiltonian path 5 → 3 → 1 → 4 → 2 is 5+8+15+10=38. Since there is no Hamiltonian path with length 39 or greater in the graph, the answer is 38.

Sample Input 2

8
2 8 8
1 5 1
4 8 2
2 5 4
3 8 6
6 8 9
2 7 12

Sample Output 2

132



Sample input:
5
1 2 5
3 4 7
2 3 3
2 5 2


Sample output:
38

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
stack = []
root = 0
dp = [[] for i in range(n+1)]
sm = [1 for i in range(n+1)]
mx = [0 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
    deg[i] += 1
ans = 0
flg = 0
while stack:
  x = stack.pop()
  if dp[x]:
    sm[x] += sum(dp[x])
  if sm[x]*2 == n:
    flg = 1
  for y,d in graph[x]:
    if deg[y] > 1:
      dp[y].append(sm[x])
      if sm[x] == n-sm[x]:
        ans += (sm[x]*2-1)*d
      else:
        ans += min(sm[x],n-sm[x])*2*d
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
dmn = 10**18
if not flg:
  for a,b,d in abd:
    for v in (a,b):
      if not mx[v]:
        if dp[v]:
          mx[v] = max(max(dp[v]),n-1-sm[v])
        else:
          mx[v] = n-2
    if min(mx[a],mx[b])*2 < n:
      dmn = min(dmn,d)
  ans -= dmn
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
if n == 2:
  print(abd[0][2])
  exit()
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
stack = []
root = 0
dp = [1 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
    deg[i] += 1
ans = 0
flg = 0
while stack:
  x = stack.pop()
  for y,d in graph[x]:
    if deg[y] > 1:
      dp[y] += dp[x]
      if dp[x] == n-dp[x]:
        flg = 1
        ans += (dp[x]*2-1)*d
      else:
        ans += min(dp[x],n-dp[x])*2*d
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if not flg:
  dmn = min(list(zip(*abd))[2])
  ans -= dmn
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
stack = []
root = 0
dp = [1 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
    deg[i] += 1
ans = 0
flg = 0
while stack:
  x = stack.pop()
  for y,d in graph[x]:
    if deg[y] > 1:
      dp[y] += dp[x]
      if dp[x] == n-dp[x]:
        flg = 1
        ans += (dp[x]*2-1)*d
      else:
        ans += min(dp[x],n-dp[x])*2*d
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if not flg:
  dmn = min(list(zip(*abd))[2])
  ans -= dmn
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main(mn=min):
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    last = [None] * (n + 1)
    xt = [None] * (3 * n - 3)
    co = [None] * (3 * n - 3)
    for i in xrange(n - 1):
        x, y, c = dat[i*3:i*3+3]
        xt[i*3] = last[y]
        xt[i*3+1] = last[x]
        last[y] = i * 3
        last[x] = i * 3 + 1
        co[i*3] = co[i*3+1] = c
    st = [1]
    pu = st.append
    po = st.pop
    d = [None] * (n + 1)
    dep = [0] * (n + 1)
    ch = [0] * (n + 1)
    ans = ok = 0
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
        else:
            ch[x] = 1
            d[x] = 1
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z]:
                    f = mn(ch[z], n - ch[z]) * 2
                    ans += co[y] * f
                    ch[x] += ch[z]
                y = xt[y]
    l = 1
    for i in xrange(1, n + 1):
        if dep[l] < dep[i]:
            l = i
    pu(l)
    dep = [0] * (n + 1)
    d = [None] * (n + 1)
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
    dd = max(dep)
    if not ok:
        mco = 1001001001
        if dd % 2:
            for i in xrange(n + 1):
                if dep[i] == dd / 2 or dep[i] == dd / 2 + 1:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        else:
            for i in xrange(n + 1):
                if dep[i] == dd / 2:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        ans -= mco
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main(mn=min):
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    last = [None] * (n + 1)
    xt = [None] * (3 * n - 3)
    co = [None] * (3 * n - 3)
    for i in xrange(n - 1):
        x, y, c = dat[i*3:i*3+3]
        xt[i*3] = last[y]
        xt[i*3+1] = last[x]
        last[y] = i * 3
        last[x] = i * 3 + 1
        co[i*3] = co[i*3+1] = c
    st = [1]
    pu = st.append
    po = st.pop
    d = [None] * (n + 1)
    dep = [0] * (n + 1)
    ch = [0] * (n + 1)
    ans = ok = 0
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
        else:
            ch[x] = 1
            d[x] = 1
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z]:
                    f = mn(ch[z], n - ch[z]) * 2
                    if f > n - 1:
                        ok = 1
                        ans += co[y] * (n - 1)
                    else:
                        ans += co[y] * f
                    ch[x] += ch[z]
                y = xt[y]
    l = 1
    for i in xrange(1, n + 1):
        if dep[l] < dep[i]:
            l = i
    pu(l)
    dep = [0] * (n + 1)
    d = [None] * (n + 1)
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
    dd = max(dep)
    if not ok:
        mco = 1001001001
        if dd % 2:
            for i in xrange(n + 1):
                if dep[i] == dd / 2 or dep[i] == dd / 2 + 1:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        else:
            for i in xrange(n + 1):
                if dep[i] == dd / 2:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        ans -= mco
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main(mn=min):
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    last = [None] * (n + 1)
    xt = [None] * (3 * n - 3)
    co = [None] * (3 * n - 3)
    for i in xrange(n - 1):
        x, y, c = dat[i*3:i*3+3]
        xt[i*3] = last[y]
        xt[i*3+1] = last[x]
        last[y] = i * 3
        last[x] = i * 3 + 1
        co[i*3] = co[i*3+1] = c
    st = [1]
    pu = st.append
    po = st.pop
    d = [None] * (n + 1)
    dep = [0] * (n + 1)
    ch = [0] * (n + 1)
    ans = ok = 0
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
        else:
            ch[x] = 1
            d[x] = 1
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z]:
                    f = mn(ch[z], n - ch[z]) * 2
                    if f > n - 1:
                        ok = 1
                        ans += co[y] * (n - 1)
                    else:
                        ans += co[y] * f
                    ch[x] += ch[z]
                y = xt[y]
    l = 1
    for i in xrange(1, n + 1):
        if dep[l] < dep[i]:
            l = i
    pu(l)
    dep = [0] * (n + 1)
    d = [None] * (n + 1)
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
    dd = max(dep)
    if not ok:
        mco = 1001001001
        if n % 2:
            for i in xrange(n + 1):
                if dep[i] == dd / 2 or dep[i] == dd / 2 + 1:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        else:
            for i in xrange(n + 1):
                if dep[i] == dd / 2:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        ans -= mco
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main(mn=min):
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    last = [None] * (n + 1)
    xt = [None] * (3 * n - 3)
    co = [None] * (3 * n - 3)
    for i in xrange(n - 1):
        x, y, c = dat[i*3:i*3+3]
        xt[i*3] = last[y]
        xt[i*3+1] = last[x]
        last[y] = i * 3
        last[x] = i * 3 + 1
        co[i*3] = co[i*3+1] = c
    st = [1]
    pu = st.append
    po = st.pop
    d = [None] * (n + 1)
    dep = [0] * (n + 1)
    ch = [0] * (n + 1)
    ans = ok = 0
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
        else:
            ch[x] = 1
            d[x] = 1
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z]:
                    f = mn(ch[z], n - ch[z]) * 2
                    if f > n - 1:
                        ok = 1
                        ans += co[y] * (n - 1)
                    else:
                        ans += co[y] * f
                    ch[x] += ch[z]
                y = xt[y]
    l = 1
    for i in xrange(1, n + 1):
        if dep[l] < dep[i]:
            l = i
    pu(l)
    dep = [0] * (n + 1)
    d = [None] * (n + 1)
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    dep[z] = dep[x] + 1
                    pu(z)
                y = xt[y]
    dd = max(dep)
    if not ok:
        mco = 1001001001
        if n % 2:
            for i in xrange(n + 1):
                if dep[i] == dd or dep[i] == dd + 1:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        else:
            for i in xrange(n + 1):
                if dep[i] == dd:
                    y = last[i]
                    while y is not None:
                        mco = mn(mco, co[y])
                        y = xt[y]
        ans -= mco
    print ans
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
def main(mn=min):
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    last = [None] * (n + 1)
    xt = [None] * (3 * n - 3)
    co = [None] * (3 * n - 3)
    mco = 1001001001
    for i in xrange(n - 1):
        x, y, c = dat[i*3:i*3+3]
        xt[i*3] = last[y]
        xt[i*3+1] = last[x]
        last[y] = i * 3
        last[x] = i * 3 + 1
        co[i*3] = co[i*3+1] = c
        mco = mn(mco, c)
    st = [1]
    pu = st.append
    po = st.pop
    d = [None] * (n + 1)
    ch = [0] * (n + 1)
    ans = ok = 0
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    pu(z)
                y = xt[y]
        else:
            ch[x] = 1
            d[x] = 1
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z]:
                    f = mn(ch[z], n - ch[z]) * 2
                    if f > n - 1:
                        ok = 1
                        ans += co[y] * (n - 1)
                    else:
                        ans += co[y] * f
                    ch[x] += ch[z]
                y = xt[y]
    if not ok:
        ans -= mco
    print ans
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
if n == 2:
  print(abd[0][2])
  exit()
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
stack = []
root = 0
dp = [[] for i in range(n+1)]
sm = [1 for i in range(n+1)]
mx = [0 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
    deg[i] += 1
ans = 0
flg = 0
while stack:
  x = stack.pop()
  if dp[x]:
    sm[x] += sum(dp[x])
  if sm[x]*2 == n:
    flg = 1
  for y,d in graph[x]:
    if deg[y] > 1:
      dp[y].append(sm[x])
      if sm[x] == n-sm[x]:
        ans += (sm[x]*2-1)*d
      else:
        ans += min(sm[x],n-sm[x])*2*d
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
dmn = 10**18
if not flg:
  for a,b,d in abd:
    for v in (a,b):
      if not mx[v]:
        if dp[v]:
          mx[v] = max(max(dp[v]),n-1-sm[v])
        else:
          mx[v] = n-2
    if min(mx[a],mx[b])*2 < n:
      dmn = min(dmn,d)
  ans -= dmn
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10**7)

N = int(readline())
ABC = (tuple(int(x) for x in line.split()) for line in readlines()) 

graph = [[] for _ in range(N+1)]
for a,b,c in ABC:
    a -= 1; b -= 1
    graph[a].append((b,c))
    graph[b].append((a,c))

# トポロジカル順序で頂点のリストを作る
V = [0]
parent = [None]
visited = [True] + [False] * (N-1)
q = [0]
while q:
    x = q.pop()
    for y,_ in graph[x]:
        if visited[y]:
            continue
        q.append(y)
        V.append(y)
        parent.append(x)
        visited[y] = True    

size = [[] for _ in range(N)] # 部分木の大きさのリスト
centroid = []
for v,p in zip(V[::-1],parent[::-1]):
    size[v].append(N-1-sum(size[v]))
    if all(x<=N//2 for x in size[v]):
        centroid.append(v)
    if p is not None:
        size[p].append(N-size[v][-1])

v0 = centroid[0]
dist = [None] * N
dist[v0] = 0
q = [v0]
while q:
    x = q.pop()
    for y,wt in graph[x]:
        if dist[y] is None:
            dist[y] = dist[x] + wt
            q.append(y)

if len(centroid) == 1:
    dist.sort()
    answer = sum(dist) * 2 - dist[0] - dist[1]
else:
    answer = sum(dist) * 2 - dist[centroid[0]] - dist[centroid[1]]
print(answer)

Submission status: Accepted

Solution code:
import sys
n=input()
sys.setrecursionlimit(n+1000)
adj=[[] for i in range(n+1)]
for i in range(n-1):
	a, b, c=map(int, raw_input().split())
	adj[a].append((b, c))
	adj[b].append((a, c))
size=[0]*(n+1)
def dfs(cur, father):
	size[cur]=1
	for to, weight in adj[cur]:
		if to!=father:
			dfs(to, cur)
			size[cur]+=size[to]
dfs(1, 0)
center=1
while True:
	change=False
	for to, weight in adj[center]:
		if size[to]<size[center] and size[to]*2>=n:
			center=to
			change=True
			break
	if not change:
		break
print>>sys.stderr, center
dfs(center, 0)
result=0
for cur in range(1, n+1):
	for to, weight in adj[cur]:
		if size[to]<size[cur]:
			result+=size[to]*weight
result*=2
print>>sys.stderr, result
for to, weight in adj[center]:
	assert size[to]*2<=n
	if size[to]*2==n:
		print>>sys.stderr, "special"
		print result-weight
		exit()
min_weight=1000000000
for to, weight in adj[center]:
	min_weight=min(min_weight, weight)
print result-min_weight

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import repeat
def main(mn=min):
    n = int(stdin.readline())
    dat = map(int, stdin.read().split(), repeat(10, 3 * n - 3))
    last = [None] * (n + 1)
    xt = [None] * (3 * n - 3)
    co = [None] * (3 * n - 3)
    for i in xrange(n - 1):
        x, y, c = dat[i*3:i*3+3]
        xt[i*3] = last[y]
        xt[i*3+1] = last[x]
        last[y] = i * 3
        last[x] = i * 3 + 1
        co[i*3] = co[i*3+1] = c
    st = [1]
    pu = st.append
    po = st.pop
    d = [None] * (n + 1)
    ch = [0] * (n + 1)
    ans = ok = 0
    ce = []
    while st:
        x = po()
        if d[x] is None:
            pu(x)
            d[x] = 0
            y = last[x]
            while y is not None:
                z = dat[y]
                if d[z] is None:
                    pu(z)
                y = xt[y]
        else:
            ch[x] = 1
            d[x] = 1
            y = last[x]
            bc = 0
            while y is not None:
                z = dat[y]
                if d[z]:
                    f = mn(ch[z], n - ch[z]) * 2
                    ans += co[y] * f
                    if ch[z] * 2 > n:
                        bc = 1
                    ch[x] += ch[z]
                y = xt[y]
            if not bc and (n - ch[x]) * 2 <= n:
                ce.append(x)
    mco = 1001001001
    if len(ce) == 2:
        i = ce[0]
        y = last[i]
        while y is not None:
            if dat[y] == ce[1]:
                mco = co[y]
            y = xt[y]
    else:
        i = ce[0]
        y = last[i]
        while y is not None:
            mco = mn(mco, co[y])
            y = xt[y]
    print ans - mco
main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
if n == 2:
  print(abd[0][2])
  exit()
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
stack = []
root = 0
dp = [1 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
    deg[i] += 1
ans = 0
flg = 0
while stack:
  x = stack.pop()
  for y,d in graph[x]:
    if deg[y] > 1:
      dp[y] += dp[x]
      if dp[x] == n-dp[x]:
        flg = 1
        ans += (dp[x]*2-1)*d
      else:
        ans += min(dp[x],n-dp[x])*2*d
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if not flg:
  print(2/0)
  dmn = min(list(zip(*abd))[2])
  ans -= dmn
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
abd = [list(map(int,input().split())) for i in range(n-1)]
if n == 2:
  print(abd[2])
  exit()
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b,d in abd:
  graph[a].append((b,d))
  graph[b].append((a,d))
  deg[a] += 1
  deg[b] += 1
stack = []
root = 0
dp = [1 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == 0:
    root = i
    deg[i] += 1
ans = 0
flg = 0
while stack:
  x = stack.pop()
  for y,d in graph[x]:
    if deg[y] > 1:
      dp[y] += dp[x]
      if dp[x] == n-dp[x]:
        flg = 1
        ans += (dp[x]*2-1)*d
      else:
        ans += min(dp[x],n-dp[x])*2*d
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
if not flg:
  dmn = min(list(zip(*abd))[2])
  ans -= dmn
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n=input()
adj=[[] for i in range(n+1)]
for i in range(n-1):
	a, b, c=map(int, raw_input().split())
	adj[a].append((b, c))
	adj[b].append((a, c))
size=[0]*(n+1)
def dfs(cur, father):
	size[cur]=1
	for to, weight in adj[cur]:
		if to!=father:
			dfs(to, cur)
			size[cur]+=size[to]
dfs(1, 0)
center=1
while True:
	change=False
	for to, weight in adj[center]:
		if size[to]<size[center] and size[to]*2>=n:
			center=to
			change=True
			break
	if not change:
		break
print>>sys.stderr, center
dfs(center, 0)
result=0
for cur in range(1, n+1):
	for to, weight in adj[cur]:
		if size[to]<size[cur]:
			result+=size[to]*weight
result*=2
print>>sys.stderr, result
for to, weight in adj[center]:
	assert size[to]*2<=n
	if size[to]*2==n:
		print>>sys.stderr, "special"
		print result-weight
		exit()
min_weight=1000000000
for to, weight in adj[center]:
	min_weight=min(min_weight, weight)
print result-min_weight