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
91
92
93
94
#include<bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair

using namespace std;

typedef long long lld;

constexpr int MAX_N = 200000;
constexpr int STEPS = 4;
constexpr long long LINF = (1ll << 60)-1;

long long mx[STEPS];
int count1, count0;
long long dp[MAX_N][STEPS];
vector<pair<int,lld> > v[MAX_N+9];

void f(int i, size_t j, long long sm) {
	if(max(-count0, count0) + count1 > (int)(v[i].size() - j)) {
		return;
	}
	
	if(j < v[i].size()) {
		lld mx_cp[STEPS];
		for(int h = 1; h < STEPS; ++h) mx_cp[h] = mx[h];
		mx[1] = max(mx[1], v[i][j].ss);
		mx[2] = max(mx[2], v[i][j].ss + dp[v[i][j].ff][1] - dp[v[i][j].ff][0]);
		mx[3] = max(mx[3], v[i][j].ss + dp[v[i][j].ff][2] - dp[v[i][j].ff][0]);
		f(i, j+1, sm + dp[v[i][j].ff][0]);
		for(int h = 1; h < STEPS; ++h) mx[h] = mx_cp[h];
		
		if(dp[v[i][j].ff][0] < v[i][j].ss + dp[v[i][j].ff][3])
			f(i, j+1, sm + v[i][j].ss + dp[v[i][j].ff][3]);
		sm += v[i][j].ss;
		count0++;
		f(i, j+1, sm + dp[v[i][j].ff][0]);
		count0 -= 2;
		f(i, j+1, sm + dp[v[i][j].ff][2]);
		count0++;
		count1 ^= 1;
		f(i, j+1, sm + dp[v[i][j].ff][1]);
		count1 ^= 1;
		return;
	}
	else {
		dp[i][0] = max(dp[i][0], sm);
		dp[i][1] = max(dp[i][1], sm + mx[1]);
		dp[i][2] = max(dp[i][2], sm + mx[2]);
		dp[i][3] = max(dp[i][3], sm + mx[3]);
	}
}

void dfs(int i, int p) {
	for(size_t j = 1; j < v[i].size(); ++j) {
		if(v[i][j].ff == p) {
			swap(v[i][j], v[i][0]);
		}
		dfs(v[i][j].ff, i);
	}
	for(int h = 1; h < STEPS; ++h) {
		dp[i][h] = -LINF;
		mx[h] = -LINF;
	}
	dp[i][0] = 0;
	count0 = 0;
	count1 = 0;
	
	f(i, 1, 0);

	
	/*
	printf("dfs:%d->%d\n", p, i);
	for(int h = 0; h < STEPS; ++h) {
		printf("dp[%d][%d] = %lld\n", i, h, dp[i][h]);
	}
	//*/
}

int main() {
	int n;
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		v[a].push_back(mp(b,c));
		v[b].push_back(mp(a,c));
	}
	v[1].push_back(mp(0,0));
	dfs(1,0);
	
	printf("%lld\n", dp[1][0]);
	return 0;
}