#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],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*N],E[N<<1];int CNT,h[N],Cnt,H[N]; void add(int u,int v,int w){e[++CNT]={u,v,w,h[u]};h[u]=CNT;} void add_side(int u,int v,int w){E[++Cnt]={u,v,w,H[u]};H[u]=Cnt;} pair<int,int> 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].sc; int v,w; for(int i=h[u];i>0;i=e[i].nx){ v=e[i].v;w=e[i].w; if(w<dis[v].fr){ dis[v]={w,i}; q.push({-w,v}); } } } } int mx,pl; bool dfs(int now,int h,int t){ vis[now]=1; if(now==t){return 1;} 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)){ if(w>mx){mx=w;pl=i;} } } return 0; } 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++){ add(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++){add_side(e[mst[i]].u,e[mst[i]].v,e[mst[i]].w);add_side(e[mst[i]].v,e[mst[i]].u,e[mst[i]].w);} int u,v,w; printf("%lld\n",ans); 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; }