#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); } inline ll read(){ char ch=getchar(); int t=1; ll num=0; while(ch<'0'||ch>'9'){ if(ch=='-')t=-1; ch=getchar(); } while('0'<=ch&&ch<='9'){ num=num*10+(ch-'0');ch=getchar(); } return t*num; } inline void write(ll num){ if(num<0)putchar('-'),num=-num; if(num<10)putchar('0'+num); else write(num/10),putchar((num%10)+'0'); } int n,q; int x[3010],y[3010]; ll dis[3010][3010]; inline int nabs(int x){ if(x>0)return x; return -x; } pair<ll,pair<int,int> >pq[9000010]; int siz=0; inline void inh(pair<ll,pair<int,int> > 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]; pair<ll,pair<int,int> > 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; ll ans,cnt; signed main(){ ios::sync_with_stdio(0); //testread(); n=read(),q=read(); for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ if(i==j)continue; ll xc=nabs(x[i]-x[j]),yc=nabs(y[i]-y[j]); dis[i][j]=dis[j][i]=xc*xc*xc+yc*yc*yc; e2[i][j]=e2[j][i]=-1000000000000000010; } } ans=0,cnt=0; memset(cost,0x3f,sizeof(cost)); cost[1]=0; inh({0,{1,1}}); while(siz){ if(cnt>=n)break; pair<ll,pair<int,int> >p=pq[1]; delh(1); if(flag[p.second.second])continue; flag[p.second.second]=1; e2[p.second.second][p.second.first]=e2[p.second.first][p.second.second]=p.first; use_edge[cnt]=p; cnt++; ans+=p.first; for(int i=1;i<=n;i++){ if(flag[i]==0)inh({dis[p.second.second][i],{p.second.second,i}}); } } cout<<ans<<endl; while(q--){ ll u=read(),v=read(),w=read(); 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].second.first),fy=top_fat(pq[1].second.second); if(fx==fy){ delh(1); continue; } use_edge[cnt]=pq[1]; cnt++; bel[fx]=fy; ans+=pq[1].first; delh(1); if(cnt>=n)break; } cout<<ans<<endl; } return 0; }