#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; } int fat[3010],bel[3010]; pair<ll,pair<int,int> > hp[6000010]; int siz=0; inline void inh(pair<ll,pair<int,int> > x){ siz++; hp[siz]=x; int fat=siz>>1,now=siz; while(fat&&hp[fat]>hp[now]){ swap(hp[fat],hp[now]); now=fat; fat>>=1; } return; } inline void delh(int x){ swap(hp[x],hp[siz]); siz--; int now=x; while((now<<1)<=siz){ int son=now<<1; if(son+1<=siz&&hp[son]>hp[son+1])son++; if(hp[son]<hp[now])swap(hp[now],hp[son]); else break; now=son; } return; } inline pair<ll,pair<int,int> > ask(int x){ return hp[x]; } ll e2[3010][3010]; bool flag[3010]; int delu,delv; ll max_del=-1000000000000000010; int stk[3010],len=0; void dfs(int x,int fa,int max_u,int max_v,ll 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){ len++; stk[len]=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); } len--; } } flag[x]=0; } 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; inh(make_pair(dis[i][j],make_pair(i,j))); } } ll ans=0; int cnt=0; for(int i=1;i<=n;i++)bel[i]=i; for(int i=1;i<=n*n;i++){ if(top_fat(ask(1).second.second)==top_fat(ask(1).second.first)){ delh(1); continue; } int x=top_fat(ask(1).second.second),y=top_fat(ask(1).second.first); bel[x]=y; e2[ask(1).second.second][ask(1).second.first]=e2[ask(1).second.first][ask(1).second.second]=ask(1).first; cnt++; ans+=ask(1).first; if(cnt==n)break; } cout<<ans<<endl; while(q--){ ll u,v,w; cin>>u>>v>>w; if(e2[u][v]!=-1000000000000000010){ ans-=e2[u][v]; e2[u][v]=min(e2[u][v],w); e2[v][u]=min(e2[v][u],w); ans+=e2[u][v]; }else{ max_del=-1000000000000000010; ans+=w; e2[u][v]=w; e2[v][u]=w; memset(flag,0,sizeof(flag)); flag[v]=1; delu=u,delv=v,max_del=-1000000000000000010; dfs(u,v,u,v,w,v); ans-=e2[delu][delv]; e2[delu][delv]=-1000000000000000010; e2[delv][delu]=-1000000000000000010; } cout<<ans<<endl; } return 0; }