#include<bits/stdc++.h> using namespace std; #define fr first #define sc second #define int long long const int N=3010,MAX=2e15+10; int n,Q,ans,cnt,x[N],y[N],e[N][N]; pair<int,int>mst[N]; int read(){ char c=getchar();int d=0,fl=1; while(c>'9'||c<'0'){ if(c=='-')fl=-1; c=getchar(); } while(c>='0'&&c<='9'){ d=d*10+c-'0';c=getchar(); } return d*fl; } int pow(int x,int y){return x*x*x+y*y*y;} struct Edge{int u,v,w,nx;}E[N<<1];int Cnt,H[N]; void add_side(int u,int v,int w){E[++Cnt]={u,v,w,H[u]};H[u]=Cnt;} struct Dis{int w,i,j;}dis[N];bool vis[N]; priority_queue<pair<int,int> >q; void prim(){ q.push({0,1});dis[1]={0,0}; while(!q.empty()){ int u=q.top().sc,len=q.top().fr;q.pop(); if(vis[u])continue;vis[u]=1; // cout<<"!"<<u<<endl; ans+=-len;mst[++cnt]={dis[u].i,dis[u].j}; int v,w; for(int v=1;v<=n;v++){ if(v==u)continue; if(e[u][v]<dis[v].w){ dis[v]={e[u][v],u,v}; q.push({-e[u][v],v}); } } } } int mx,pl; bool dfs(int now,int h,int t){ vis[now]=1; if(now==t){return 1;} bool flag=0; for(int i=H[now];i>0;i=E[i].nx){ int v=E[i].v,w=E[i].w; if(vis[v])continue; if(dfs(v,h,t)){ flag=1; if(w>mx){mx=w;pl=i;} } } return flag; } void del(int id){ int u=E[id].u,v=E[id].v,w=E[id].w,lst=0; for(int i=H[u];i>0;i=E[i].nx){ int vv=E[i].v,ww=E[i].w; if(vv==v){ if(i==H[u]){H[u]=E[i].nx;break;} else{E[lst].nx=E[i].nx;break;} } lst=i; } u=E[id].v;v=E[id].u; for(int i=H[u];i>0;i=E[i].nx){ int vv=E[i].v,ww=E[i].w; if(vv==v){ if(i==H[u]){H[u]=E[i].nx;break;} else{E[lst].nx=E[i].nx;break;} } lst=i; } } signed main(){ for(int i=0;i<=N-5;i++){dis[i]={MAX,0};} 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=1;j<=n;j++){ e[i][j]=pow(abs(x[i]-x[j]),abs(y[i]-y[j])); // cout<<i<<" "<<j<<" "<<pow(abs(x[i]-x[j]),abs(y[i]-y[j]))<<endl; } } prim(); for(int i=2;i<=n;i++){ int u=mst[i].fr,v=mst[i].sc; add_side(u,v,e[u][v]);add_side(v,u,e[u][v]); // cout<<u<<" "<<v<<" "<<e[u][v]<<endl; } printf("%lld\n",ans); int u,v,w; while(Q--){ u=read();v=read();w=read(); for(int i=1;i<=n;i++)vis[i]=0; mx=-MAX; dfs(u,u,v); if(mx>w){ ans-=E[pl].w; del(pl); add_side(u,v,w);add_side(v,u,w); ans+=w; } printf("%lld\n",ans); } return 0; }