#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; } int fat[3010],bel[3010]; priority_queue<pair<int,pair<int,int> > >pq; vector<int>e[3010]; int e2[3010][3010]; bool flag[3010]; int delu,delv,max_del=-1000000000000000010; int stk[3010],len=0; 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){ 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(){ //testread2(); 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; pq.push(make_pair(-dis[i][j],make_pair(i,j))); } } int 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(pq.top().second.second)==top_fat(pq.top().second.first)){ pq.pop(); continue; } int x=top_fat(pq.top().second.second),y=top_fat(pq.top().second.first); bel[x]=y; e2[pq.top().second.second][pq.top().second.first]=e2[pq.top().second.first][pq.top().second.second]=-pq.top().first; cnt++; ans-=pq.top().first; if(cnt==n)break; } cout<<ans<<endl; while(q--){ int 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; }