1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int,int> pp;
typedef long long ll;
const ll inf=1000000000000000000;
vector<vector<pp>> graph;
vector<int> up;
mt19937 rng(1337^21237);
struct wyn
{
	ll v0,v1,v2,v3;
};
vector<wyn> dp;
ll gwyn=-inf;
ll pref[2][2402][2];
void dfs(int p,int oj)
{
	
	vector<int> kol={-10};
	for(auto I : graph[p])
	{
		if(I.ff!=oj)
		{
			up[I.ff]=I.ss;
			dfs(I.ff,p);
			kol.pb(I.ff);
		}
	}
	kol.pb(-10);
	int il=(int)kol.size()-2;

	if(il==0)
	{
		dp[p].v1=max(dp[p].v1,(ll)up[p]);
		return;
	}
//	for(auto I : kol)	printf("%d ",I);
//	printf("\n");
	shuffle(kol.begin()+1,kol.end()-1,rng);
//	for(auto I : kol)	printf("%d ",I);
//	printf("\n");
	int bsize=min(1200,il+1);
	
	for(int i=0;i<=1;++i)	for(int j=0;j<=2*bsize+1;++j)	pref[i][j][0]=pref[i][j][1]=-inf;
	pref[0][bsize][0]=0;
//	printf("------\n%d: %d\n",p,il);
//	for(auto I : kol)	printf("%d ",I);
//	printf("\n");
	for(int i=1;i<=il;++i)
	{
		int I=kol[i];
		for(int j=1;j<=2*bsize;++j)
		{
			pref[i&1][j][0]=max({pref[(i^1)&1][j][0]+dp[I].v0,pref[(i^1)&1][j-1][0]+dp[I].v1,pref[(i^1)&1][j][1]+dp[I].v2,pref[(i^1)&1][j+1][0]+dp[I].v3});
			pref[i&1][j][1]=max({pref[(i^1)&1][j][1]+dp[I].v0,pref[(i^1)&1][j-1][1]+dp[I].v1,pref[(i^1)&1][j][0]+dp[I].v2,pref[(i^1)&1][j+1][1]+dp[I].v3});
		}
		for(int j=1;j<=2*bsize;++j)	pref[(i^1)&1][j][0]=pref[(i^1)&1][j][1]=-inf;
	}
	ll t0=max(0LL,pref[il&1][bsize][0]),t1=pref[il&1][bsize+1][0],t2=pref[il&1][bsize][1],t3=pref[il&1][bsize-1][0];
	
	if(p==1)	gwyn=t0;
	dp[p].v0=max({dp[p].v0,t0,t3+up[p]});
	dp[p].v1=max({dp[p].v1,t0+up[p]});
	dp[p].v2=max({dp[p].v2,t1+up[p]});
	dp[p].v3=max({dp[p].v3,t2+up[p]});
//	printf("%d   %lld %lld %lld %lld   %lld %lld %lld %lld\n",p,t0,t1,t2,t3,dp[p].v0,dp[p].v1,dp[p].v2,dp[p].v3);
}

int main()
{
	int n;
	scanf("%d",&n);
	graph.resize(n+1);
	dp.resize(n+1);
	up.resize(n+1);
	for(int i=1;i<n;++i)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		graph[a].pb(mp(b,c));
		graph[b].pb(mp(a,c));
	}
	fill(dp.begin(),dp.end(),(wyn){0,-inf,-inf,-inf});
	dfs(1,0);
	printf("%lld\n",gwyn);
}