#include<bits/stdc++.h> #define ll long long using namespace std; int n,q; ll x[3005],y[3005]; struct dsu{ int fa[3005],sz[3005]; inline void init(){ for(int i=1;i<=n;i++)fa[i]=i,sz[i]=1; } inline int fr(int p){ // cout<<p<<" "; return fa[p]==p?p:(fa[p]=fr(fa[p])); } inline void mg(int x,int y){ // cout<<x<<" "<<y<<endl; x=fr(x),y=fr(y); if(x==y)return; if(sz[x]>sz[y])swap(x,y); fa[x]=y; sz[y]+=sz[x]; } }D; struct edge{ int u,v; ll w; }T[int(5e6)]; inline bool operator<(edge a,edge b){ return a.w<b.w; } vector<edge>e_; vector<int>e[100005]; inline ll calc(int a,int b){ return abs(x[a]-x[b])*(x[a]-x[b])*(x[a]-x[b])+abs(y[a]-y[b])*(y[a]-y[b])*(y[a]-y[b]); } template<typename T> inline void read(T &x){ x=0; bool f=0; char c=getchar(); while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x; }ll lz[600005],vl[600005],fa[600005],ch[600005][2],id[600005],mx[600005]; void pu(int x){ mx[x]=vl[x],id[x]=x; if(mx[ch[x][0]]>mx[x])mx[x]=mx[ch[x][0]],id[x]=id[ch[x][0]]; if(mx[ch[x][1]]>mx[x])mx[x]=mx[ch[x][1]],id[x]=id[ch[x][1]]; return; } void tr(int x){ swap(ch[x][0],ch[x][1]); lz[x]^=1; return; } void pd(int x){ if(!lz[x])return; if(ch[x][0])tr(ch[x][0]); if(ch[x][1])tr(ch[x][1]); lz[x]=0; return; } bool nr(int x){ return ch[fa[x]][0]==x||ch[fa[x]][1]==x; } bool get(int x){ return ch[fa[x]][1]==x; } void rot(int x){ int y=fa[x],z=fa[y],c=get(x); if(nr(y))ch[z][get(y)]=x; fa[x]=z; ch[y][c]=ch[x][!c]; if(ch[x][!c])fa[ch[x][!c]]=y; ch[x][!c]=y; fa[y]=x; pu(y); pu(x); return; } void upd(int x){ if(nr(x))upd(fa[x]); pd(x); return; } void splay(int x){ upd(x); for(int f=fa[x];nr(x);rot(x),f=fa[x]) if(nr(f))rot(get(x)==get(f)?f:x); return; } int acs(int x){ int p=0; for(;x;p=x,x=fa[p]){ splay(x),ch[x][1]=p,pu(x); } return p; } void mkr(int x){ acs(x),splay(x),tr(x); return; } int fr(int x){ acs(x),splay(x),pd(x); while(ch[x][0])x=ch[x][0],pd(x); return splay(x),x; } void split(int x,int y){ mkr(x),acs(y),splay(y); return; } void link(int x,int y){ mkr(x); if(fr(y)!=x)fa[x]=y; return; } bool chk(int x,int y){ return fr(x)==fr(y); } int cnt=0; signed main(){ //freopen("slpjbh.out","r",stdin); //freopen("slpjbh.in","w",stdout); read(n),read(q); for(int i=1;i<=n;i++)read(x[i]),read(y[i]); for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ T[cnt++]={i,j,calc(i,j)}; } } sort(T,T+cnt); e_.resize(cnt); for(int i=0;i<cnt;++i)e_[i]=T[i]; ll ans=0; D.init(); int tot=n; for(auto x:e_){ if(D.fr(x.u)!=D.fr(x.v)){ D.mg(x.u,x.v); vl[++tot]=x.w; link(x.u,tot); link(x.v,tot); ans+=x.w; } } printf("%lld\n",ans); // e_.resize(0); // cout<<e_.capacity()*sizeof(int)/1024/1024<<endl; for(int i=1;i<=q;i++){ ll a,b,c; read(a),read(b),read(c); split(a,b);int p=id[b]; // cout<<mx[b]<<" "<<c<<endl; if(mx[b]<=c){ cout<<ans<<endl; continue; } ans=ans-mx[b]+c; splay(p); fa[ch[p][0]]=fa[ch[p][1]]=0; vl[i+n+n]=c; link(a,i+n+n),link(b,i+n+n); cout<<ans<<endl; } return 0; }