#include<bits/stdc++.h> #define ll long long using namespace std; void testread(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); } void testread2(){ freopen("logistics.in","r",stdin); freopen("logistics.out","w",stdout); } int n,q; int x[3010],y[3010]; ll dis[3010][3010]; inline int nabs(int x){ if(x>0)return x; return -x; } struct pt{ ll cost; int l,r; bool operator<(pt a) const{return cost<a.cost;} bool operator>(pt a) const{return cost>a.cost;} }; pt pq[9000010]; int siz=0; inline void inh(pt x){ siz++; pq[siz]=x; int fat=siz>>1,now=siz; while(fat&&pq[fat]>pq[now]){ swap(pq[fat],pq[now]); now=fat; fat>>=1; } return; } inline void delh(int x){ swap(pq[x],pq[siz]); siz--; int now=x; while((now<<1)<=siz){ int son=now<<1; if(son+1<=siz&&pq[son]>pq[son+1])son++; if(pq[son]<pq[now])swap(pq[now],pq[son]); else break; now=son; } return; } ll e2[3010][3010]; bool flag[3010]; int fat[3010],bel[3010]; ll cost[3010]; pt use_edge[3010]; inline int top_fat(int x){ if(bel[x]!=x){ bel[x]=top_fat(bel[x]); return bel[x]; } return x; } int fx,fy; signed main(){ //testread(); cin>>n>>q; for(int i=1;i<=n;i++)cin>>x[i]>>y[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j)continue; ll xc=nabs(x[i]-x[j]),yc=nabs(y[i]-y[j]); dis[i][j]=xc*xc*xc+yc*yc*yc; e2[i][j]=-1000000000000000010; } } ll ans=0,cnt=0; memset(cost,0x3f,sizeof(cost)); cost[1]=0; inh({0,1,1}); while(siz){ if(cnt>=n)break; pt p=pq[1]; delh(1); if(flag[p.r])continue; flag[p.r]=1; e2[p.r][p.l]=e2[p.l][p.r]=p.cost; use_edge[cnt]=p; cnt++; ans+=p.cost; for(int i=1;i<=n;i++){ if(flag[i]==0)inh({dis[p.r][i],p.r,i}); } } cout<<ans<<endl; while(q--){ int u,v; ll w; cin>>u>>v>>w; siz=0; for(int i=1;i<n;i++){inh(use_edge[i]);} inh({w,u,v}); ans=0,cnt=1; for(int i=1;i<=n;i++)bel[i]=i; while(siz){ fx=top_fat(pq[1].l),fy=top_fat(pq[1].r); if(fx==fy){ delh(1); continue; } use_edge[cnt]=pq[1]; cnt++; bel[fx]=fy; ans+=pq[1].cost; delh(1); if(cnt>=n)break; } cout<<ans<<endl; } return 0; }