#include "bits/stdc++.h"
#include "nile.h"
#define ll long long
#define sz(v) (ll) v.size()
#define all(v) v.begin(),v.end()
using namespace std;
const ll N = 1e5 + 5;
const ll INF = 1e18;
ll par[N], siz[N], tot, ans[N], mini[N][2] ,L[N], bsum[N], acik[N];
vector<array<ll,3>> ar;
ll find(ll a){
if(par[a] == a) return a;
return par[a] = find(par[a]);
}
void unite(ll a,ll b){
//cout << "birles : " << a << ' ' << b << '\n';
if(a + 2 == b){
acik[find(a)] = min(acik[find(a)], ar[a + 1][2] - ar[a + 1][1]);
if(siz[find(a)] % 2){
tot -= ans[find(a)];
ans[find(a)] = min(ans[find(a)], bsum[find(a)] + acik[find(a)]);
tot += ans[find(a)];
}
//cout << "new cost : " << ans[a] << '\n';
return;
}
a=find(a),b=find(b);
if(a==b) return;
if(siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
L[a] = min(L[a], L[b]);
tot -= (ans[a] + ans[b]);
ans[a] += ans[b];
acik[a] = min(acik[a], acik[b]);
for(int i=0;i<2;i++) mini[a][i] = min(mini[a][i], mini[b][i]);
bsum[a] += bsum[b];
//cout << "old cost : " << ans[a] << '\n';
if(siz[a] % 2){
//cout << "wtf1 : " << bsum[a] + mini[a][L[a]&1] << '\n';
//cout << "wtf2 : " << bsum[a] + acik[a] << '\n';
ans[a] = min(ans[a], bsum[a] + mini[a][L[a]&1]);
ans[a] = min(ans[a], bsum[a] + acik[a]);
}
else{
ans[a] = min(ans[a], bsum[a]);
}
// cout << "new cost : " << ans[a] << '\n';
tot += ans[a];
}
vector<ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
ll n = sz(W);
ar.clear();
for(ll i=0;i<n;i++){
ll a = W[i], b = B[i], c = A[i];
ar.push_back({a, b, c});
}
sort(all(ar));
ll q = sz(E);
vector<ll> Res(q, 0);
vector<array<ll,2>> que;
for(ll i=0;i<q;i++){
ll a = E[i];
que.push_back({a, i});
}
sort(all(que));
tot = 0;
for(ll i=0;i<n;i++){
L[i] = par[i] = i;
acik[i] = INF;
siz[i] = 1;
mini[i][i&1] = ar[i][2] - ar[i][1];
mini[i][!(i&1)] = INF;
bsum[i] = ar[i][1];
ans[i] = ar[i][2];
tot += ans[i];
}
vector<array<ll,3>> Merge;
for(ll i=1;i<n;i++) Merge.push_back({ar[i][0] - ar[i - 1][0], 0, i - 1});
for(ll i=1;i+1<n;i++) Merge.push_back({ar[i+1][0] - ar[i-1][0], 1, i - 1});
sort(all(Merge));
ll ptr = 0;
for(array<ll,2> x : que){
while(ptr < sz(Merge) && Merge[ptr][0] <= x[0]){
if(Merge[ptr][1] == 0) unite(Merge[ptr][2] , Merge[ptr][2] + 1);
else unite(Merge[ptr][2], Merge[ptr][2] + 2);
ptr++;
}
Res[x[1]] = tot;
}
return Res;
}
/*void _(){
int n;
cin >> n;
for(int i=0;i<n;i++){
int a,b,c;
cin >> a >> b >> c;
ar.push_back({a, c, b});
}
sort(all(ar));
int q; cin >> q;
vector<ll> Res(q, 0);
vector<array<ll,2>> que;
for(int i=0;i<q;i++){
int a; cin >> a;
que.push_back({a, i});
}
sort(all(que));
tot = 0;
for(ll i=0;i<n;i++){
L[i] = par[i] = i;
acik[i] = INF;
siz[i] = 1;
mini[i][i&1] = (ar[i][2] - ar[i][1]);
mini[i][!(i&1)] = INF;
bsum[i] = ar[i][1];
ans[i] = ar[i][2];
tot += ans[i];
}
vector<array<ll,3>> Merge;
for(ll i=1;i<n;i++) Merge.push_back({ar[i][0] - ar[i - 1][0], 0, i - 1});
for(ll i=1;i+1<n;i++) Merge.push_back({ar[i+1][0] - ar[i-1][0], 1, i - 1});
sort(all(Merge));
ll ptr = 0;
for(array<ll,2> x : que){
while(ptr < sz(Merge) && Merge[ptr][0] <= x[0]){
if(Merge[ptr][1] == 0) unite(Merge[ptr][2] , Merge[ptr][2] + 1);
else unite(Merge[ptr][2], Merge[ptr][2] + 2);
ptr++;
}
Res[x[1]] = tot;
}
for(int i=0;i<q;i++){
cout << Res[i] << '\n';
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int tc=1;//cin >> tc;
while(tc--) _();
}*/
