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
#include<bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

vector<int> vis;
vector<vector<pair<int,int>>> G;
vector<vector<int>> T;


int p(int a,int b){
	if(a==LLONG_MIN||b==LLONG_MIN)
		return LLONG_MIN;
	return a+b;
}


vector<int> foo(int v){
	
	vector<int> in;
	vector<int> wg;
	for(auto x:G[v]) if(vis[x.first]==2) { in.push_back(x.first); wg.push_back(x.second);}
	if(in.size()==0) return vector<int>({0, LLONG_MIN,LLONG_MIN,LLONG_MIN});

	
	for(int i=0;i<in.size();i++)
		T[in[i]]=vector<int>({
			max(T[in[i]][0], p(wg[i],T[in[i]][3])),
			p(wg[i],T[in[i]][0]),
			p(wg[i],T[in[i]][1]),
			p(wg[i],T[in[i]][2])
		});

	
	int n = in.size();
	int L = n/2+1;
	int l = L+1;
	

		
	vector<vector<int>> dpOld(2*L+4, vector<int>(2, LLONG_MIN));
	vector<vector<int>> dpNew(2*L+4, vector<int>(2, LLONG_MIN));	
	dpOld[0+l][0]=0;
		//dłoguść prefiksu, różnica 1-3, parzystość 2
	
	for(int i=1;i<=n;i++) { for(int j=-L;j<=L;j++) for(int k=0;k<2;k++)
		dpNew[j+l][k]= max({
			p(dpOld[j+l][k]   , T[in[i-1]][0]),
			p(dpOld[j+l][1-k] , T[in[i-1]][2]),
			p(dpOld[j-1+l][k] , T[in[i-1]][1]),
			p(dpOld[j+1+l][k] , T[in[i-1]][3])
		});
		dpOld=dpNew;
	}
	
	return vector<int>({
		dpNew[0+l][0],
		dpNew[1+l][0],
		dpNew[0+l][1],
		dpNew[-1+l][0]
	});
	
	
}


void DFS(int v){
	vis[v]=1;
	for(auto x:G[v]){
		int w = x.first;
		if(vis[w]==0) DFS(w);
	} 

	vector<int> F= foo(v);
	T[v] = F;
	vis[v]=2;
}







int32_t main(){

	ios::sync_with_stdio(false); cin.tie(NULL);
		
	int n;cin>>n;
	
	G = vector<vector<pair<int,int>>>(n);
	vis = vector<int>(n);
	T = vector<vector<int>>(n, vector<int>(4, LLONG_MIN));
	
	for(int i=0;i<n-1;i++){
		int k1,k2,k3;
		cin>>k1>>k2>>k3;
		k1--;k2--;
		G[k1].push_back({k2,k3});
		G[k2].push_back({k1,k3});
	}

	DFS(0);

	cout <<T[0][0];
	
}