#include<bits/stdc++.h> #define int 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]; int dis[3010][3010]; inline int nabs(int x){ if(x>0)return x; return -x; } pair<int,pair<int,int> >pq[9000010]; int siz=0; inline void inh(pair<int,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<int,pair<int,int> > ask(int x){ return pq[x]; } int e2[3010][3010]; bool flag[3010]; int delu,delv,max_del=-1000000000000000010; int stk[3010],len=0; inline void dfs(int x,int fa,int max_u,int max_v,int max_dis,int end){ if(flag[x]){ if(max_del<max_dis){ delu=max_u; delv=max_v; max_del=max_dis; } return; } flag[x]=1; for(int i=1;i<=n;i++){ if(e2[x][i]!=-1000000000000000010&&i!=fa&&x!=i){ if(max_dis<e2[x][i]){ dfs(i,x,i,x,e2[x][i],end); }else{ dfs(i,x,max_u,max_v,max_dis,end); } } } } int fat[3010],bel[3010]; int cost[3010]; pair<int,pair<int,int> > use_edge[3010]; 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; int 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; } } int 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<int,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; while(q--){ int u,v,w; cin>>u>>v>>w; siz=0; for(int i=1;i<=cnt;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; for(int i=1;i<=n*n;i++){ 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); cnt++; use_edge[cnt]=ask(1); bel[x]=y; ans+=ask(1).first; delh(1); if(cnt>=n)break; } cout<<ans<<endl; } return 0; }