#include<bits/stdc++.h> using namespace std; #define int long long int n,q,idx; const int N=3010; int f[N],siz[N]; struct node{ int x,y; }a[N]; struct node2{ int i,j; long long d; }b[N*1500],c[N]; bool cmp(node2 x,node2 y){ return x.d<y.d; } int find(int x){ if(f[x]!=x) f[x]=find(f[x]); return f[x]; } signed main(){ //freopen("logistics.in","r",stdin); //freopen("logistics.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); cin>>n>>q; //cout<<"###"; for(int i=1;i<=n;i++){ siz[i]=1; f[i]=i; cin>>a[i].x>>a[i].y; for(int j=1;j<i;j++){ b[++idx].i=j; b[idx].j=i; b[idx].d=abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y); } } sort(b+1,b+1+idx,cmp); //cout<<"!!!"; int k=1; long long ans=0; for(int i=1;i<=idx&&k<n;i++){ int x=find(b[i].i); int y=find(b[i].j); if(x!=y){ if(siz[x]<siz[y]) swap(x,y); siz[y]+=siz[x]; f[y]=x; ans+=b[i].d; b[k]=b[i]; k++; } } printf("%lld\n",ans); if(q==0){ return 0; } for(int i=1;i<=q;i++){ int x,y,z; cin>>x>>y>>z; //b[k]=node2{x,y,z}; for(int j=1;j<=n;j++){ siz[j]=1; f[j]=j; }ans=0; int l=-1,r=n; for(int j=1;j<n;j++){ if(b[j].d<z){ int x=find(b[j].i); int y=find(b[j].j); if(x!=y){ if(siz[x]<siz[y]) swap(x,y); siz[y]+=siz[x]; f[y]=x; ans+=b[j].d; } } else { if(l==-1){ int x1=find(x); int y1=find(y); if(x1!=y1){ if(siz[x1]<siz[y1]) swap(x1,y1); siz[y1]+=siz[x1]; f[y1]=x1; ans+=z; l=j; } else l=0; } int x=find(b[j].i); int y=find(b[j].j); if(x!=y){ if(siz[x]<siz[y]) swap(x,y); siz[y]+=siz[x]; f[y]=x; ans+=b[j].d; } else r=j; } //cout<<j<<" "<<ans<<endl; } if(l>0){ for(int j=r;j>l;j--) b[j]=b[j-1]; b[l].i=x; b[l].j=y; b[l].d=z; } printf("%lld\n",ans); } }