#include<bits/stdc++.h> #define int long long using namespace std; void testread(){ freopen("test.in","r",stdin); freopen("test.out","w",stdout); } void testread2(){ freopen("logistics.in","r",stdin); freopen("logistics.out","w",stdout); } int n,q; int x[3010],y[3010]; int dis[3010][3010]; inline int nabs(int x){ if(x>0)return x; return -x; } priority_queue<pair<int,pair<int,int> > >pq; int e2[3010][3010]; bool flag[3010]; int delu,delv,max_del=-1000000000000000010; int stk[3010],len=0; void dfs(int x,int fa,int max_u,int max_v,int max_dis,int end){ if(flag[x]){ if(max_del<max_dis){ delu=max_u; delv=max_v; max_del=max_dis; } return; } flag[x]=1; for(int i=1;i<=n;i++){ if(e2[x][i]!=-1000000000000000010&&i!=fa&&x!=i){ len++; stk[len]=i; if(max_dis<e2[x][i]){ dfs(i,x,i,x,e2[x][i],end); }else{ dfs(i,x,max_u,max_v,max_dis,end); } len--; } } flag[x]=0; } int cost[3010]; signed main(){ //testread(); cin>>n>>q; for(int i=1;i<=n;i++)cin>>x[i]>>y[i]; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i==j)continue; int xc=nabs(x[i]-x[j]),yc=nabs(y[i]-y[j]); dis[i][j]=xc*xc*xc+yc*yc*yc; e2[i][j]=-1000000000000000010; } } int ans=0,cnt=0; memset(cost,0x3f,sizeof(cost)); cost[1]=0; pq.push(make_pair(0,make_pair(1,1))); while(!pq.empty()){ if(cnt>=n)break; pair<int,pair<int,int> >p=pq.top(); pq.pop(); if(flag[p.second.second])continue; flag[p.second.second]=1; e2[p.second.second][p.second.first]=e2[p.second.first][p.second.second]=-p.first; cnt++; ans-=p.first; for(int i=1;i<=n;i++){ if(flag[i]==0)pq.push(make_pair(-dis[p.second.second][i],make_pair(p.second.second,i))); } } cout<<ans<<endl; while(q--){ int u,v,w; cin>>u>>v>>w; if(e2[u][v]!=-1000000000000000010){ ans-=e2[u][v]; e2[u][v]=min(e2[u][v],w); e2[v][u]=min(e2[v][u],w); ans+=e2[u][v]; }else{ max_del=-1000000000000000010; ans+=w; e2[u][v]=w; e2[v][u]=w; memset(flag,0,sizeof(flag)); flag[v]=1; delu=u,delv=v,max_del=-1000000000000000010; dfs(u,v,u,v,w,v); ans-=e2[delu][delv]; e2[delu][delv]=-1000000000000000010; e2[delv][delu]=-1000000000000000010; } cout<<ans<<endl; } return 0; }