#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=300005, Mod=1e9+7;

struct SegTree
{
    struct Node
    {
        ll sum=0, pre=0, suf=0, len=0;
        Node(){}

        Node (ll x): sum(x), pre(x), suf(x), len(1){}

        Node operator + (const Node &o) const 
        {
            Node ans;
            ans.len=len+o.len;
            ans.sum=sum+o.sum+suf*o.pre;
            ans.pre=pre==len?pre+o.pre:pre;
            ans.suf=o.suf==o.len?o.suf+suf:o.suf;
            return ans;
        }
    };

    ll n;
    vector <Node> St;

    void build(ll i, ll Start, ll End, ll v)
    {
        if (Start==End) {St[i]=Node(v); return;}
        ll mid=(Start+End)/2;
        build(i*2, Start, mid, v);
        build(i*2+1, mid+1, End, v);
        St[i]=St[i*2]+St[i*2+1];
    }
    SegTree(ll n, ll v): n(n){St.resize(n*4+1), build(1, 0, n-1, v);}

    void update(ll i, ll Start, ll End, ll idx, ll v)
    {
        if (Start==End) {St[i]=Node(v); return;}
        ll mid=(Start+End)/2;
        if (mid>=idx) update(i*2, Start, mid, idx, v);
        else update(i*2+1, mid+1, End, idx, v);
        St[i]=St[i*2]+St[i*2+1];
    }
    void update(ll idx, ll v){update(1, 0, n-1, idx, v);}

    ll query(){return St[1].sum;}
};

int maintenance_costs_sum(std::vector<int> U, std::vector<int> V, std::vector<int> W) 
{
    ll n=sz(W)+1;
    vector <vector <pll>> A(n);
	for (ll i=0; i<sz(W); i++)
        A[U[i]].pb({V[i], W[i]}), A[V[i]].pb({U[i], W[i]});
    // all nodes in subtree i is marked with val, all nodes outside marked with val^1
    auto solve=[&](ll val)
    {
        SegTree S(n, val^1);
        vector <ll> ans(n, 0), child(n, 0), big(n, -1);
        function <void(ll, ll)> predfs=[&](ll u, ll pa)
        {
            child[u]=1;
            for (auto [v, w]:A[u])
            {
                if (v==pa) continue;
                predfs(v, u), child[u]+=child[v];
                if (big[u]==-1 || child[big[u]]<child[v]) big[u]=v;
            }
        }; predfs(0, 0);
        function <void(ll, ll, ll)> mark=[&](ll u, ll pa, ll c)
        {
            S.update(u, c);
            for (auto [v, w]:A[u])
                if (v!=pa)
                    mark(v, u, c);
        };
        function <void(ll, ll)> calc=[&](ll u, ll pa)
        {
            for (auto [v, w]:A[u])
                if (v!=pa && v!=big[u])
                    calc(v, u), mark(v, u, val^1);
            if (big[u]!=-1) calc(big[u], u);
            for (auto [v, w]:A[u])
                if (v!=pa && v!=big[u])
                    mark(v, u, val);
            S.update(u, val);
            ans[u]=S.query();
        }; calc(0, 0);
        return ans;
    };
    ll answer=0;
    vector <ll> cnt[2];
    cnt[0]=solve(0), cnt[1]=solve(1);
    function <void(ll, ll)> getans=[&](ll u, ll pa)
    {
        for (auto [v, w]:A[u])
            if (v!=pa)
            {
                answer+=w*(n*(n+1)/2-cnt[0][v]-cnt[1][v]);
                getans(v, u);
            }
    }; getans(0, 0);
    return answer;
}