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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define PPC(x) __builtin_popcountll(x)
#define MSB(x) (63 - __builtin_clzll(x))
#define LSB(x) __builtin_ctz(x)
#define ARG(x, i) (get<i>(x))
#define ithBit(m, i) ((m) >> (i) & 1)
#define pb push_back
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std; 

template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b);	}
template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b);	}
 
const int maxN = 1 << 18;
const long long INF = 1'0000'0000'0000'0000;

vector <pair <int, int> > G[maxN];
long long dp[maxN][4];
int state[maxN];
long long T[maxN][2][2];

void go(int v)
{
	int I = 1, s = SZ(G[v]) / 2 + 1;
	FOR(i, -1, s+1) FOR(a, 0, 2) FOR(b, 0, 2)
		T[I + i][a][b] = -INF;
	T[I + 0][0][0] = 0;
	
	FOR(i, 1, SZ(G[v])+1)
	{
		int u = G[v][i-1].ft;
		int a = i & 1, z = a ^ 1, mx = min(i, s);
		
		FOR(j, -1, mx + 1) FOR(d, 0, 2)
		{
			auto& x = T[I + j][a][d];
			x = T[I + j][z][d] + dp[u][1];
			if (j != mx)
				remax(x, T[I + j+1][z][d] + dp[u][0]);
			if (j != -1)
				remax(x, T[I + j-1][z][d] + dp[u][2]);
			remax(x, T[I + j][z][d ^ 1] + dp[u][3]);				
		}
	}
	
	s = SZ(G[v]) & 1;
	dp[v][0] = T[I + 0][s][0];
	dp[v][1] = T[I + 1][s][0];
	dp[v][2] = T[I + 0][s][1];
	dp[v][3] = T[I - 1][s][0];
}

void dfs(int v, int fat = 0)
{
	FOR(i, 0, SZ(G[v]))
	{
		int u = G[v][i].ft;
		if (u == fat)
		{
			swap(G[v][i], G[v].back());
			G[v].pop_back();
			i--;
			continue;
		}
		dfs(u, v);
	}
			
	sort(ALL(G[v]), [] (auto& a, auto& b)
	{
		int u = a.ft, w = b.ft;
		return dp[u][2] - dp[u][0] > dp[w][2] - dp[w][0];
	});
	
	for (auto [u, e] : G[v])
	{
		dp[u][1] += e;
		remax(dp[u][1], dp[u][0]);
		state[u] = 1;
		FOR(i, 0, 4) if (i != 1)
		{
			dp[u][i] += e;
			if (dp[u][i] > dp[u][state[u]])
				state[u] = i;				
		} 
	}
	
	go(v);
}

void solve()
{
	int n;
	scanf ("%d", &n);
	FOR(i, 1, n)
	{
		int a, b, c;
		scanf ("%d%d%d", &a, &b, &c);
		G[a].pb({b, c});
		G[b].pb({a, c});
	}
	
	dfs(1, 0);
	printf("%lld\n", dp[1][0]);
}
 
int main()
{
	int t = 1;
	//scanf ("%d", &t);
	FOR(tid, 1, t+1)
	{
		//printf("Case #%d: ", tid);
		solve();
	}
	return 0;
}