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
130
// #pragma GCC optimize "O3"
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define PR std::pair
#define MP std::make_pair
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;
#define WEZ(a, b) if((a) < (b)) a = b;

constexpr int S = 850;
constexpr int AS = 2 * S + 2;

int fun(int ile){
	if(ile < 1) ile = 1;
	auto xd = std::min(S, std::max(450, (int)(std::sqrt(1.0 * ile) * 3.8 + (50000 - ile) / 50000.0 * 75.0)));
	return xd;
}

constexpr ll INF = 1'000'000'000ll * 1'000'000'000ll;
std::mt19937 mt1337(387581);
template<typename T> void shuffle(std::vector<T>& t){ std::shuffle(t.begin(), t.end(), mt1337); }

std::vector<std::vector<PII>> g;
ll dp[200005][4];
ll ddd[2][AS][2][4];
typedef std::array<ll, 4> AR;

void dfs(int v, int par=-1){
	std::vector<AR> vec;
	vec.reserve(par == -1 ? SZ(g[v]) : SZ(g[v]) - 1);
	shuffle(g[v]);

	int big = 0;
	TRAV(ch, g[v]) if(ch.X != par){
		dfs(ch.X, v);
		vec.push_back({std::max(dp[ch.X][0], dp[ch.X][3] + ch.Y), dp[ch.X][0] + ch.Y, dp[ch.X][1] + ch.Y, dp[ch.X][2] + ch.Y});
		if(vec.back()[3] > -INF / 2){
			big++;
		}
	}

	const int RS = fun(big);
	const int RA = RS * 2 + 2;

	// if(big > 1000)
	// 	std::cerr << RS << " | " << big << std::endl;

	if(SZ(vec) == 0){
		dp[v][0] = 0;
		REP(i, 1, 4) dp[v][i] = -INF;
		return;
	}

	int ja = 0;
	int on = 1;
	FOR(i, RA) FOR(j, 2) FOR(k, 4) ddd[ja][i][j][k] = -INF;
	// std::fill(&ddd[ja][0][0][0], &ddd[ja][0][0][0] + sizeof(ddd) / sizeof(ddd[0][0][0][0]), -INF);
	ddd[ja][RS][0][0] = 0;
	FOR(ind, SZ(vec)){
		std::swap(ja, on);

		// const auto ar = vec[ind];
		const ll a = vec[ind][0];
		const ll b = vec[ind][1];
		const ll c = vec[ind][2];
		const ll d = vec[ind][3];
		// FOR(i, RA) FOR(j, 2) FOR(k, 4) ddd[ja][i][j][k] = -INF;
		// std::fill(&ddd[ja][0][0][0], &ddd[ja][0][0][0] + sizeof(ddd[ja]) / sizeof(ddd[0][0][0][0]), -INF);

		int zost = SZ(vec) - ind + 4;
		int from = std::max(1, RS - zost);
		int to = std::min(RA-1, RS + zost);

		FOR(j, 2) FOR(k, 4) ddd[ja][from-1][j][k] = ddd[ja][to][j][k] = -INF;
		REP(i, from, to) FOR(j, 2){
			FOR(k, 4){
				ddd[ja][i][j][k] = ddd[on][i][j][k] + a;
				// WEZ(ddd[ja][i][j][k], ddd[on][i][j][k] + a);
				WEZ(ddd[ja][i][j][k], ddd[on][i][j^1][k] + c);
				WEZ(ddd[ja][i][j][k], ddd[on][i-1][j][k] + d);
				WEZ(ddd[ja][i][j][k], ddd[on][i+1][j][k] + b);
			}

			// REP(k, 1, 4){
			// 	WEZ(ddd[ja][i][j][k], ddd[on][i][j][0] + ar[k]);
			// }
			WEZ(ddd[ja][i][j][1], ddd[on][i][j][0] + b);
			WEZ(ddd[ja][i][j][2], ddd[on][i][j][0] + c);
			WEZ(ddd[ja][i][j][3], ddd[on][i][j][0] + d);
		}
	}

	FOR(k, 4){
		dp[v][k] = ddd[ja][RS][0][k];
	}
}

class eee { std::string name_; };

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	int n;
	std::cin >> n;
	g.resize(n);
	FOR(i, n-1){
		int a, b, c;
		std::cin >> a >> b >> c;
		a--;b--;
		g[a].push_back(MP(b, c));
		g[b].push_back(MP(a, c));
	}

	eee ee;

	std::srand(666);
	int root = std::rand()%n;
	FOR(i, n) FOR(j, 4) dp[i][j] = -INF;
	dfs(root);
	std::cout << dp[root][0] << "\n";

	return 0;
}