#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef long long ll;

vector<multiset<pair<ll,ll>>> g;
vector<ll> val,val2;
ll ans=0ll;

void izracunaj(int c, int p){
    val[c]=0ll;
    for(auto a: g[c]){
        if(a.fi==p)continue;
        izracunaj(a.fi,c);
        if(a.se+val[a.fi]>=val[c]){
            val2[c]=val[c];
            val[c]=a.se+val[a.fi];
        }else if(a.se+val[a.fi]>=val2[c])val2[c]=a.se+val[a.fi];
    }
}

ll zbir(int c){
    ll m1=-1ll;
    ll m2=-1ll;
    ll m3=-1ll;
    if(g[c].size()<3)return 0ll;
    for(auto a:g[c]){
        //cout<<a.fi<<' '<<a.se<<"    ";
        //cout<<m1<<' '<<m2<<' '<<m3<<endl;
        if(a.se+val[a.fi]>=m1){
            m3=m2;
            m2=m1;
            m1=a.se+val[a.fi];
        }
        else if(a.se+val[a.fi]>=m2){
            m3=m2;
            m2=a.se+val[a.fi];
        }
        else if(a.se+val[a.fi]>=m3)m3=a.se+val[a.fi];
    }

    return m1+m2+m3;
}

void resi(int c, int p){
    ans=max(ans,zbir(c));
    val[c]=0ll;
    for(auto a: g[c]){
        if(a.se+val[a.fi]>=val[c]){
            val2[c]=val[c];
            val[c]=a.se+val[a.fi];
        }else if(a.se+val[a.fi]>=val2[c])val2[c]=a.se+val[a.fi];
    }

    for(auto a:g[c]){
        if(a.fi==p)continue;
        int tmp=val[c];
        if(val[a.fi]+a.se==val[c])val[c]=val2[c];
        resi(a.fi,c);
        val[c]=tmp;
    }

}

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* odg){
    if(n*n*q>5000*5000)return;
    g.resize(n+1);
    for(int i=0;i<=n;i++)g[i].clear();
    for(int i=2;i<=n;i++){
        g[i].insert({(ll)p[i],(ll)w[i]});
        g[p[i]].insert({(ll)i,(ll)w[i]});
    }
    /*
    for(int i=1;i<=n;i++){
        cout<<i<<": ";
        for(auto a:g[i])cout<<'('<<a.fi<<','<<a.se<<')'<<' ';
        cout<<endl;
    }
*/
    for(int e=1;e<=q;e++){
        ans=0ll;
        int i=s[e];
        //cout<<i<<' '<<p[i]<<' '<<w[i]<<endl;
        //if(g[i].find({(ll)p[i],(ll)w[i]})==g[i].end())cout<<"nee"<<endl;
        //else cout<<"da"<<endl;
        g[i].erase(g[i].find({(ll)p[i],(ll)w[i]}));
        //cout<<"aaa"<<endl;
        g[p[i]].erase(g[p[i]].find({(ll)i,(ll)w[i]}));

        g[i].insert({p[i],k[e]});
        g[p[i]].insert({i,k[e]});
        w[i]=k[e];
        val.assign(n+1,0ll);

        val2.assign(n+1,0ll);
        for(int i=1;i<=n;i++){
            izracunaj(i,0);
            ans=max(ans, zbir(i));
        }


        odg[e]=ans;
    }
    //cout<<endl<<endl;

    return;
}