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
#include <algorithm>
#include <cstdio>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define VAR(v,w) __typeof(w) v=(w)
#define FORE(it,c) for(VAR(it,(c).begin());it!=(c).end();++it)
#define PB push_back
#define SIZE(c) ((int)(c).size())
#define MP make_pair
#define FT first
#define SD second
#define INT(x) int x; scanf("%d", &x)

typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<LL> VLL;

const LL INF = 1000000000000000000LL;
vector<VII> g;
LL res[200000][4];

bool next(VI& v) {
	int i = 0, n = SIZE(v);
	while (i < n && v[i] == 3) v[i++] = 0;
	if (i == n) return 0;
	++v[i];
	return 1;
}

void go(int v, int p) {
	vector<VLL> r;
	FORE(it,g[v]) {
		int w = it->FT;
		if (w == p) continue;
		int z = it->SD;
		go(w, v);
		VLL rr(4);
		rr[0] = max(res[w][0], res[w][3] + z);
		rr[1] = res[w][0] + z;
		rr[2] = res[w][1] + z;
		rr[3] = res[w][2] + z;
		r.PB(rr);
	}
	int n = SIZE(r);
	VI vv(n);
	REP(x,4) res[v][x] = -INF;
	do {
		VI c(4);
		FORE(it,vv) ++c[*it];
		int x = -1;
		if (c[1] == c[3]) {
			if (c[2] & 1) x = 2;
			else x = 0;
		} else if (c[1] == c[3] + 1 && !(c[2] & 1)) x = 1;
		else if (c[1] + 1 == c[3] && !(c[2] & 1)) x = 3;
		if (x == -1) continue;
		LL s = 0;
		REP(i,n) s += r[i][vv[i]];
		res[v][x] = max(res[v][x], s);
	} while (next(vv));
}

int main() {
	INT(n);
	g.resize(n);
	REP(i,n-1) {
		INT(u);
		INT(v);
		INT(z);
		--u;
		--v;
		g[u].PB(MP(v, z));
		g[v].PB(MP(u, z));
	}
	go(0, -1);
	printf("%lld\n", res[0][0]);
}