#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; 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); } ll ans=0; ll dis[100005]; int mstid[100005]; bool vis[100005]; void prim(){ memset(dis,0x3f,sizeof dis); dis[1]=0; for(int i=1;i<=n;i++){ int u=0; for(int j=1;j<=n;j++){ if(!vis[j]&&(!u||dis[u]>dis[j]))u=j; } vis[u]=1; if(mstid[u]){ vl[i+n]=calc(u,mstid[u]); ans+=calc(u,mstid[u]); link(u,i+n); link(i+n,mstid[u]); } for(int j=1;j<=n;j++){ if(!vis[j]&&calc(u,j)<dis[j]){ dis[j]=calc(j,u); mstid[j]=u; } } } } 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]); prim(); printf("%lld\n",ans); for(int i=1;i<=q;i++){ ll a,b,c; read(a),read(b),read(c); split(a,b);int p=id[b]; 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; }