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
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

#define st first
#define nd second
#define PII pair <int, int>

const int N = 200'007;
const int C = 1200;
const LL INF = 1'001'002'003'004'005'006LL;

int n;
LL results[N][5];
vector <PII> G[N];
int max_deg;

int m;
LL dp[2][2][2 * C + 1];

void remax(LL &v, const LL a) 
{
    v = max(v, a);
}

void calc_dp(int u, int par) 
{
    vector <tuple <LL, LL, LL, LL> > states;
    for (const auto &[v, c]: G[u]) {
        if (v == par) {
            continue;
        }

        LL c1 = c + results[v][0];
        LL c2 = c + results[v][1];
        LL c3 = c + results[v][2];
        LL c4 = max(c + results[v][3], results[v][4]);
        states.push_back({c1, c2, c3, c4});
    }

    results[u][4] = 0;
    results[u][0] = 0;
    for (int t = 1; t < 4; ++t) {
        results[u][t] = -INF;
    }

    if (states.size() == 0) {
        return;
    }

    dp[0][0][C] = 0;
    dp[0][1][C] = -INF;

    random_shuffle(states.begin(), states.end());
    for (int p = 0; p < (int)states.size(); ++p) {
        auto [c1, c2, c3, c4] = states[p];

        int s = min(p + 1, C);
        int t = p + 1 & 1;

        for (int i = 0; i < 2; ++i)
            for (int j = -s; j <= s; ++j)
                dp[t][i][j + C] = -INF;
        
        for (int i = 0; i < 2; ++i) {
            for (int j = -s + 1; j < s; ++j) {
                remax(dp[t][i][j + C], dp[t ^ 1][i][j + C] + c4);
                remax(dp[t][i ^ 1][j + C], dp[t ^ 1][i][j + C] + c2);

                if (j + 1 <= C) {
                    remax(dp[t][i][j + 1 + C], dp[t ^ 1][i][j + C] + c3);
                }

                if (j - 1 >= -C) {
                    remax(dp[t][i][j - 1 + C], dp[t ^ 1][i][j + C] + c1);
                }
            }
        }
    }

    int t = states.size() & 1;
    results[u][0] = dp[t][0][C];
    results[u][1] = dp[t][0][C - 1];
    results[u][2] = dp[t][1][C];
    results[u][3] = dp[t][0][C + 1];
    results[u][4] = dp[t][0][C];
}

void dfs(int u, int p) 
{
    for (const auto &[v, _]: G[u]) {
        if (v != p) {
            dfs(v, u);
        }
    }

    max_deg = max(max_deg, (int)G[u].size());
    calc_dp(u, p);
}

int main() 
{
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);

        G[u].push_back({v, c});
        G[v].push_back({u, c});
    }

    dfs(1, 1);
    printf("%lld\n", results[1][4]);
    return 0;
}