#include<bits/stdc++.h> #define ll long long #define endl '\n' using namespace std; const int maxn=3007; const int maxm=4500007; const ll B=1e5+1; const ll INF=6e18; const ll BP[3]={1,B,B*B}; //basic struct Poi{ int x,y; }P[maxn]; inline ll Cub(int x){return 1ll*x*x*x;} inline ll Val(Poi A,Poi B){return Cub(abs(A.x-B.x))+Cub(abs(A.y-B.y));} int n,q; struct ed{ int u,v; ll w; ed(int _u=0,int _v=0,ll _w=0){u=_u,v=_v,w=_w;} }eg[maxm]; queue<ed> buc[B+7]; int cnt; //Kruskal //Radix sort M * log_B M \approx 3e7 inline void RadixSort(){ for(int r=0;r<3;r++){ for(int i=1;i<=cnt;i++){ ll c=eg[i].w; c=(c/BP[r])%B; buc[c].push(eg[i]); } int tot=0; for(int i=0;i<B;i++)while(!buc[i].empty())eg[++tot]=buc[i].front(),buc[i].pop(); } } struct DSU{ int f[maxn],siz[maxn]; inline void Init(){for(int i=1;i<=n;i++)f[i]=i,siz[i]=1;} inline int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);} inline bool Eq(int x,int y){return Find(x)==Find(y);} inline void MG(int x,int y){ int fx=Find(x),fy=Find(y); if(fx==fy)return; if(siz[fx]>siz[fy])swap(fx,fy); f[fx]=fy,siz[fy]+=siz[fx]; } }F; struct Edge{ int v; ll w; Edge(int _v=0,ll _w=0){v=_v,w=_w;} }; vector<Edge> E[maxn]; inline void Print(){ for(int u=1;u<=n;u++)for(auto e:E[u])if(e.v>u)cout<<u<<" "<<e.v<<" "<<e.w<<endl; } inline void Kruskal(){ RadixSort(); F.Init(); int EC=0; for(int i=1;i<=cnt;i++){ if(F.Eq(eg[i].u,eg[i].v))continue; EC++; E[eg[i].u].push_back(Edge(eg[i].v,eg[i].w)); E[eg[i].v].push_back(Edge(eg[i].u,eg[i].w)); F.MG(eg[i].u,eg[i].v); if(EC>=n-1)break; } } //Rebuild ll up[maxn]; ll SV[maxn]; int f[maxn]; int d[maxn]; inline void Rebuild(int u){ SV[u]=0; d[u]=d[f[u]]+1; for(auto e:E[u]){ int v=e.v;ll w=e.w; if(v==f[u])continue; up[v]=w;f[v]=u;Rebuild(v); SV[u]+=(SV[v]+w); } } inline void Link(int u,int v,ll w){ E[u].push_back(Edge(v,w)); E[v].push_back(Edge(u,w)); } inline void Cut(int u,int v){ vector<Edge> cur;cur.clear(); for(auto e:E[u]){ if(e.v==v)continue; cur.push_back(e); } E[u]=cur; cur.clear(); for(auto e:E[v]){ if(e.v==u)continue; cur.push_back(e); } E[v]=cur; cur.clear(); } inline ed Qmax(int u,int v){ if(d[u]<d[v])swap(u,v); ed ret(0,0,0); while(d[u]>d[v]){ ll w=up[u]; if(w>ret.w)ret=ed(u,f[u],w); u=f[u]; } while(u!=v){ ll w=up[u]; if(w>ret.w)ret=ed(u,f[u],w);u=f[u]; w=up[v]; if(w>ret.w)ret=ed(v,f[v],w);v=f[v]; } return ret; } inline void ChMST(int u,int v,ll w){ ed e=Qmax(u,v); int MU=e.u,MV=e.v; if(e.w<w)return; Cut(MU,MV); Link(u,v,w); Rebuild(1); } signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifndef ONLINE_JUDGE freopen("logistics.in","r",stdin); freopen("logistics.out","w",stdout); #endif cin>>n>>q; for(int i=1;i<=n;i++)cin>>P[i].x>>P[i].y; for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)eg[++cnt]=ed(i,j,Val(P[i],P[j])); Kruskal(); Rebuild(1); cout<<SV[1]<<endl; while(q--){ int u,v; ll w; cin>>u>>v>>w; ChMST(u,v,w); cout<<SV[1]<<endl; }cout.flush(); return 0; }