#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; } 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; } inline pair<ll,pair<int,int> > ask(int x){ return pq[x]; } 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; } 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(make_pair(0,make_pair(1,1))); while(siz){ if(cnt>=n)break; pair<ll,pair<int,int> >p=ask(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(make_pair(dis[p.second.second][i],make_pair(p.second.second,i))); } } cout<<ans<<endl; q/=2; while(q--){ ll u,v,w; cin>>u>>v>>w; siz=0; for(int i=1;i<=n;i++){inh(use_edge[i]);} inh(make_pair(w,make_pair(u,v))); ans=0,cnt=1; for(int i=1;i<=n;i++)bel[i]=i; while(siz){ if(top_fat(ask(1).second.first)==top_fat(ask(1).second.second)){ delh(1); continue; } int x=top_fat(ask(1).second.first),y=top_fat(ask(1).second.second); use_edge[cnt]=ask(1); cnt++; bel[x]=y; ans+=ask(1).first; delh(1); if(cnt>=n)break; } cout<<ans<<endl; } return 0; }