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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7;
const ll INF=1e18+7;
vector<pair<ll,ll>>V[LIM];
ll dp[LIM][4];
void DFS(int x, int o) {
	if(x && V[x].size()==1) return;
	vector<ll>T[4];
	for(auto i : V[x]) if(i.st!=o) {
		DFS(i.st, x);
		T[0].pb(max(dp[i.st][0], dp[i.st][3]+i.nd));
		rep(j, 3) T[j+1].pb(dp[i.st][j]+i.nd);
	}
	ll P[2*V[x].size()+10][2];
	rep(i, 2*V[x].size()+10) rep(j, 2) P[i][j]=-INF;
	P[V[x].size()+2][0]=0;
	rep(i, T[0].size()) {
		ll K[2*V[x].size()+10][2];
		rep(j, 2*V[x].size()+10) rep(l, 2) K[j][l]=-INF;
		rep(j, 2*V[x].size()+10) rep(l, 2) {
			K[j][l]=max(K[j][l], P[j][l]+T[0][i]);
			K[j][l^1]=max(K[j][l^1], P[j][l]+T[2][i]);
			if(j) {
				K[j-1][l]=max(K[j-1][l], P[j][l]+T[3][i]);
			}
			if(j<2*V[x].size()+9) {
				K[j+1][l]=max(K[j+1][l], P[j][l]+T[1][i]);
			}
		}
		rep(j, 2*V[x].size()+10) rep(l, 2) P[j][l]=K[j][l];
	}
	dp[x][0]=max(dp[x][0], P[V[x].size()+2][0]);
	dp[x][1]=max(dp[x][1], P[V[x].size()+3][0]);
	dp[x][2]=max(dp[x][2], P[V[x].size()+2][1]);
	dp[x][3]=max(dp[x][3], P[V[x].size()+1][0]);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	cin >> n;
	rep(i, n-1) {
		int a, b, c;
		cin >> a >> b >> c; --a; --b;
		V[a].pb({b, c});
		V[b].pb({a, c});
	}
	rep(i, n) rep(j, 3) dp[i][j+1]=-INF;
	DFS(0, 0);
	cout << dp[0][0] << '\n';
}