#include<bits/stdc++.h> #define pii pair<int,int> #define pll pair<ll,ll> #define pli pair<ll,int> #define fi first #define se second #define mk make_pair #define ll long long using namespace std; //io #define isd(ch) ((ch)>='0'&&(ch)<='9') #define gc getchar #define pc putchar inline ll read(){ ll t=0;int f=1;char ch=gc(); while(!isd(ch)){ if(ch=='-') f=-1;ch=gc(); }while(isd(ch)) t=t*10+ch-'0',ch=gc(); return t*f; }char sta[25]; inline void write(ll x){ int top=0;(x<0)?pc('-'),x=-x:x=x; if(x==0) pc('0'); while(x>0) sta[++top]=x%10+'0',x/=10; while(top>0) pc(sta[top--]); } #define wtln() pc('\n'); //read const int N=3050; const ll inf=1e18+10; struct edge{ int u,v;ll w; }; vector<pll> G[N]; vector<edge> E; int n,q; ll val=0; pli d[N];bool vis[N]; #define p3(x) (x)*(x)*(x) ll dis(ll a,ll b,ll c,ll d){ return p3(abs(a-c))+p3(abs(b-d)); } int x[N],y[N]; void prim(){ for(int i=1;i<=n;i++) d[i]=mk(inf,0); d[1]=mk(0,0);vis[1]=1; int now=1; for(int i=1;i<n;i++){ vis[now]=1; pli mn=mk(inf,0); for(int j=1;j<=n;j++){ if(vis[j]) continue; d[j]=min(d[j],mk(dis(x[now],y[now],x[j],y[j]),now)); //cout<<d[j].fi<<' '<<j<<' '<<now<<endl; mn=min(mn,mk(d[j].fi,j)); }val+=mn.fi; E.push_back((edge){d[mn.se].se,mn.se,mn.fi}); now=mn.se; } } bool eq(edge a,edge b){ if(a.u==b.u&&a.v==b.v) return 1; if(a.u==b.v&&a.v==b.u) return 1; return 0; }int to[N];ll vl[N]; void dfs(int u,int fa){ to[u]=fa;//cout<<u<<endl; for(auto ed:G[u]){ int v=ed.fi;ll w=ed.se; if(v==fa) continue; vl[v]=w;dfs(v,u); } } void upd(int u,int v,ll w){ edge eg=(edge){u,v,w}; for(auto &ed:E){ if(eq(ed,eg)){ if(eg.w<ed.w){ val-=ed.w;val+=eg.w;ed.w=eg.w; return ; } } }for(int i=1;i<=n;i++) G[i].clear(); for(auto ed:E) G[ed.u].push_back(mk(ed.v,ed.w)),G[ed.v].push_back(mk(ed.u,ed.w)); dfs(u,0); int now=v;pli mx=mk(0,0); while(now!=u){ //cout<<vl[now]<<' '; mx=max(mk(vl[now],now),mx); now=to[now]; }//cout<<mx.fi<<' '<<w<<endl; if(mx.fi>w){ for(auto &ed:E){ if(eq(ed,(edge){mx.se,to[mx.se],0})){ val-=ed.w;val+=w; ed=(edge){u,v,w}; return ; } } } } int main(){ n=read(),q=read(); for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();prim(); write(val);wtln(); //for(auto ed:E) cout<<ed.u<<' '<<ed.v<<' '<<ed.w<<' '<<endl; while(q--){ int u=read(),v=read();ll w=read(); upd(u,v,w); write(val);wtln(); } return 0; }