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
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
#include <assert.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
Edgc
int n;
struct F {
ll w[4];
}g[200055];
struct G {
ll w[3];
}t[SZ];
int vn;
#define S 1500
ll f[2][2][S+S+2];
inline void chkmax(ll&a,ll b) {
	if(a<b)a=b;
}
void dp(int x,int fa=0) {
	for esb(x,e,b) if(b!=fa) dp(b,x);
	vn=0; ll ans=0;
	for esb(x,e,b) if(b!=fa) {
		ll v=vc[e];
		ll f1=g[b].w[0]+v;
		ll f2=g[b].w[1]+v;
		ll f3=g[b].w[2]+v;
		ll f4=max(g[b].w[3]+v,max(g[b].w[0],0LL));
		f1-=f4; f2-=f4; f3-=f4; ans+=f4;
		t[++vn].w[0]=f1; t[vn].w[1]=f3; t[vn].w[2]=f2;
	}
	random_shuffle(t+1,t+1+vn);
	int c=0;
	memset(f[c],-127/3,sizeof f[c]);
	f[c][0][S]=0;
	const ll bad=-3.5e18;
	for(int i=1;i<=vn;++i) {
		c^=1;
		memcpy(f[c],f[c^1],sizeof f[c]);
		ll F;
		for(int j=0;j<2;++j)
			for(int k=1;k<S+S;++k) if((F=f[c^1][j][k])>=bad) {
				chkmax(f[c][j][k+1],F+t[i].w[0]);
				chkmax(f[c][j][k-1],F+t[i].w[1]);
				chkmax(f[c][j^1][k],F+t[i].w[2]);
			}
	}
	g[x].w[0]=f[c][0][S]+ans;
	g[x].w[1]=f[c][0][S+1]+ans;
	g[x].w[2]=f[c][1][S]+ans;
	g[x].w[3]=f[c][0][S-1]+ans;
//	cout<<x<<":"<<g[x].w[0]<<","<<g[x].w[1]<<","<<g[x].w[2]<<","<<g[x].w[3]<<"?\n";
}
int main()
{
	scanf("%d",&n);
	for(int i=1,a,b,c;i<n;++i)
		scanf("%d%d%d",&a,&b,&c),
		adde(a,b,c);
	dp(1);
	printf("%lld\n",max(g[1].w[0],0LL));
}