#include<bits/stdc++.h> using namespace std; const int N = 3010; int n,q,ind[N],od[N],bz[N],ind2[N],od2[N],vis[N],cnt,Q[N],P[N]; long long int maxn,maxnx,maxny,ans; long long int dis[N]; vector<pair<int,long long int> > G[N]; struct E{ long long int x; long long int y; long long int w; }e[N],num[N]; struct T{ long long int x; long long int y; }a[N]; struct Q{ long long int x; long long int y; long long int w; }b[N]; bool cmp(E z,E q){ return z.w<q.w; } void dfs(int x,int ac){ vis[x]=1; for(int i=0;i<G[x].size();i++){ int v=G[x][i].first; long long int w=G[x][i].second; if(v==ac){ if(w>maxn){ maxn=w; maxnx=x; maxny=v; } } if(vis[v]||bz[v]) continue; if(w>maxn){ maxn=w; maxnx=x; maxny=v; } dfs(v,ac); } } void Prim(int op){ for(int i=1;i<=n;i++) dis[i]=1e18; for(int i=1;i<=n;i++) vis[i]=0; for(int j=1;j<=n;j++){ long long int w=(a[1].x-a[j].x)*(a[1].x-a[j].x)*(a[1].x-a[j].x); long long int w2=(a[1].y-a[j].y)*(a[1].y-a[j].y)*(a[1].y-a[j].y); if(w<0){ w=-w; } if(w2<0){ w2=-w2; } w=w+w2; if(dis[j]>w){ dis[j]=w; P[j]=1; } } for(int j=1;j<=cnt;j++){ if(e[j].x==1){ if(dis[e[j].y]>e[j].w){ dis[e[j].y]=e[j].w; P[e[j].y]=1; } } } vis[1]=1; int l=1,r=0; Q[++r]=1; while(r-l+1<n){ long long int minn=1e18; int tmp=-1; for(int i=1;i<=n;i++){ if(minn>dis[i]&&!vis[i]){ minn=dis[i]; tmp=i; } } if(op==1){ ind[Q[r]]++; od[Q[r]]++; ind[tmp]++; od[tmp]++; G[Q[r]].push_back(make_pair(tmp,minn)); G[tmp].push_back(make_pair(Q[r],minn)); } ans+=minn; for(int i=1;i<=n;i++){ long long int w=(a[tmp].x-a[i].x)*(a[tmp].x-a[i].x)*(a[tmp].x-a[i].x); long long int w2=(a[tmp].y-a[i].y)*(a[tmp].y-a[i].y)*(a[tmp].y-a[i].y); if(w<0) w=-w; if(w2<0) w2=-w2; w=w+w2; if(dis[i]>w){ dis[i]=w; P[i]=tmp; } } for(int i=1;i<=cnt;i++){ if(e[i].x==tmp){ if(dis[e[i].y]>e[i].w){ dis[e[i].y]=e[i].w; P[e[i].y]=tmp; } } } vis[tmp]=1; Q[++r]=tmp; } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].y; } for(int i=1;i<=q;i++){ cin>>b[i].x>>b[i].y>>b[i].w; } if(q==0){ Prim(0); cout<<ans<<endl; exit(0); } else if(n<=100&&q<=100){ Prim(0); cout<<ans<<endl; for(int i=1;i<=q;i++){ ans=0; ++cnt; e[cnt].x=b[i].x; e[cnt].y=b[i].y; e[cnt].w=b[i].w; ++cnt; e[cnt].x=b[i].y; e[cnt].y=b[i].x; e[cnt].w=b[i].w; Prim(0); cout<<ans<<endl; } exit(0); } if(n<=3000){ Prim(1); cout<<ans<<endl; for(int i=1;i<=q;i++){ for(int j=1;j<=n;j++){ ind2[j]=0; od2[j]=0; vis[j]=0; bz[j]=0; } long long int f=0; for(int j=0;j<G[b[i].x].size();j++){ int v=G[b[i].x][j].first; long long int w=G[b[i].x][j].second; if(v==b[i].y){ f=w; break; } } if(f){ if(b[i].w<f){ int tot=0; for(int j=0;j<G[b[i].x].size();j++){ ++tot; num[tot].y=G[b[i].x][j].first; num[tot].w=G[b[i].x][j].second; num[tot].x=b[i].x; } G[b[i].x].clear(); for(int j=1;j<=tot;j++){ if(num[j].x==b[i].x&&num[j].y==b[i].y&&num[j].w==f){ continue; } G[num[j].x].push_back(make_pair(num[j].y,num[j].w)); } tot=0; for(int j=0;j<G[b[i].y].size();j++){ ++tot; num[tot].y=G[b[i].y][j].first; num[tot].w=G[b[i].y][j].second; num[tot].x=b[i].y; } G[b[i].y].clear(); for(int j=1;j<=tot;j++){ if(num[j].x==b[i].y&&num[j].y==b[i].x&&num[j].w==f){ continue; } G[num[j].x].push_back(make_pair(num[j].y,num[j].w)); } G[b[i].x].push_back(make_pair(b[i].y,b[i].w)); G[b[i].y].push_back(make_pair(b[i].x,b[i].w)); ans=ans-f; ans=ans+b[i].w; cout<<ans<<endl; } else{ cout<<ans<<endl; } continue; } G[b[i].x].push_back(make_pair(b[i].y,b[i].w)); G[b[i].y].push_back(make_pair(b[i].x,b[i].w)); ind2[b[i].x]++; od2[b[i].x]++; ind2[b[i].y]++; od2[b[i].y]++; int l=1,r=0; for(int j=1;j<=n;j++){ ind2[j]+=ind[j]; od2[j]+=od[j]; if(ind2[j]==1&&od2[j]==1){ Q[++r]=j; } } while(r-l+1>=1){ int x=Q[l]; l++; bz[x]=1; for(int j=0;j<G[x].size();j++){ int v=G[x][j].first; ind2[v]--; od2[v]--; if(ind2[v]==1&&od2[v]==1){ Q[++r]=v; } } } int tmp=0; for(int j=1;j<=n;j++){ if(bz[j]==0){ tmp=j; break; } } maxn=0; maxnx=0; maxny=0; dfs(tmp,tmp); int tot=0; for(int j=0;j<G[maxnx].size();j++){ ++tot; num[tot].y=G[maxnx][j].first; num[tot].w=G[maxnx][j].second; num[tot].x=maxnx; } G[maxnx].clear(); for(int j=1;j<=tot;j++){ if(num[j].x==maxnx&&num[j].y==maxny&&num[j].w==maxn){ continue; } G[num[j].x].push_back(make_pair(num[j].y,num[j].w)); } tot=0; for(int j=0;j<G[maxny].size();j++){ ++tot; num[tot].y=G[maxny][j].first; num[tot].w=G[maxny][j].second; num[tot].x=maxny; } G[maxny].clear(); for(int j=1;j<=tot;j++){ if(num[j].x==maxny&&num[j].y==maxnx&&num[j].w==maxn){ continue; } G[num[j].x].push_back(make_pair(num[j].y,num[j].w)); } if(maxnx==b[i].x&&maxny==b[i].y&&maxn==b[i].w){ cout<<ans<<endl; continue; } if(maxnx==b[i].y&&maxny==b[i].x&&maxn==b[i].w){ cout<<ans<<endl; continue; } ind[b[i].x]++; od[b[i].x]++; ind[b[i].y]++; od[b[i].y]++; ind[maxnx]--; od[maxnx]--; ind[maxny]--; od[maxny]--; ans=ans-maxn; ans=ans+b[i].w; cout<<ans<<endl; } } return 0; }