从一条边出发遍历，每次找旋转角度最小的一条边作为下一条边，直到回到出发的边，就得到了一个区域。这样建出对偶图后跑不定根的最小树形图就行了。
#include<cstdio>
#include<cmath>
#include<map>
#define ub upper_bound
using namespace std;
const int N=5005;
map<double,int>s[N];
int sum,n,m,q[N],v[N];
struct edge{
int v,w;
edge*s;
}e[N*2];
edge*l=e,*h[N];
void add(int u,int v,int w){
sum+=w;
edge s={v,w,h[u]};
*(h[u]=l++)=s;
}
struct vec{
int x,y;
double a;
vec(){}
vec(int x,int y):x(x),y(y),a(atan2(y,x)){}
}a[N];
vec operator-(vec a,vec b){
return vec(a.x-b.x,a.y-b.y);
}
namespace dual{
struct edge{
int u,v,w;
}e[N*2];
edge*l=e;
void add(int u,int v,int w){
edge s={u,v,w};
*l++=s;
}
int d[N],p[N],s[N],t[N];
int find(int&v){
for(int i=1;i!=n;++i){
s[i]=0;
d[i]=1e9;
}
for(edge*i=e;i!=l;++i)
if(d[i->v]>i->w){
p[i->v]=i->u;
d[i->v]=i->w;
}
int now=0;
for(int i=1;i!=n;++i){
v+=d[i];
int u=i;
for(;u&&!s[u];u=p[u])
s[u]=i;
now+=s[u]==i;
for(;s[u]==i;u=p[u]){
s[u]=-1;
t[u]=now;
}
}
return now;
}
int sol(int v){
while(int now=find(v)){
for(int i=1;i!=n;++i)
if(~s[i])t[i]=++now;
n=now+1;
edge*q=l;
for(edge*i=l=e;i!=q;++i)
if(t[i->u]!=t[i->v])
add(t[i->u],t[i->v],i->w-d[i->v]);
}
return v;
}
}
struct buf{
char z[1<<20],*s;
buf():s(z){
z[fread(z,1,sizeof z,stdin)]=0;
}
operator int(){
int x=0,y=0;
while(*s<48)
if(*s++==45)y=1;
while(*s>32)
x=x*10+*s++-48;
return y?-x:x;
}
}it;
int sol(){
for(int i=1;i<=n;++i)
for(edge*j=h[i];j;j=j->s)
s[i][(a[j->v]-a[i]).a]=j-e;
for(int i=1;i<=n;++i)
for(edge*j=h[i];j;j=j->s){
typeof(s->end())u=s[j->v].ub((a[i]-a[j->v]).a);
if(s[j->v].end()==u)
u=s[j->v].begin();
q[j-e]=u->second;
}
using dual::add;
using dual::sol;
int&now=n=1;
for(edge*i=e;i!=l;++i)
if(!v[i-e]){
for(int j=i-e;!v[j];j=q[j])
v[j]=now;
add(0,now++,sum);
}
for(edge*i=e;i!=l;++i)
if(i->w)
add(v[i-e^1],v[i-e],i->w);
return sol(-sum);
}
int main(){
n=it,m=it;
for(int i=1;i<=n;++i){
a[i].x=it;
a[i].y=it;
}
while(m--){
int s=it,t=it;
add(s,t,it);
add(t,s,it);
}
printf("%d
",sol());
}