Description：

给一个凸多边形上的一些点，有 $m$ 条防御网连接这些点其中的两个点，每条防御网有伤害，问从 $S$ 到 $T$ 受到伤害最少是多少。

$1\le n\le 100000$ $1\le m \le 100000$

Solution：

有两种路线可以选，一是直接从 $S$ 走到 $T$ ，二是从 $S$ 走到多边形外再走到 $T$ ，对于第一种情况，由于是凸多边形，所以 $S$ 和 $T$ 在直线两边的直线一定会造成伤害，只要把 $S$ 和 $v$ ， $T$ 和 $v$ 叉积值不相同的直线伤害加起来即可，对于第二种情况，可以分别求出 $S$ 和 $T$ 从每条边走出多边形的伤害，具体做法是把多边形断开，那么每道防御网都会使连续一个区间（或 $[1,l]\cup[r,n]$ ）的边的值加上这道防御网的伤害，只要判断一下 $S$ 或 $T$ 在边的哪一边即可。可以差分之后求前缀和。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define INF 0x3f3f3f3f3f3f3f3f

inline int read()

{

	register int res = 0;

	register int f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

struct point

{

	double x,y;

	point(double x_ = 0.0,double y_ = 0.0){x = x_;y = y_;}

	friend point operator + (point a,point b){return point(a.x + b.x,a.y + b.y);}

	friend point operator - (point a,point b){return point(a.x - b.x,a.y - b.y);}

	friend double dot(point a,point b){return a.x * b.x + a.y * b.y;}

	friend double cross(point a,point b){return a.x * b.y - a.y * b.x;}

}p[MAXN],s,t;

struct line

{

	point p,v;

	line(){};

	line(point p_,point v_){p = p_;v = v_;}

}l[MAXN];

typedef long long ll;

ll u[MAXN],v[MAXN],c[MAXN];

ll val[MAXN];

#define eps 1e-6

bool equal(double a,double b){return fabs(a - b) <= eps;}

int sign(double k){return (equal(k,0.0) ? 0 : (k < 0 ? -1 : 1));}

bool in(point k)

{

	for(int i = 1;i <= n;++i)

		if(sign(cross(l[i].v,k - l[i].p)) < 0)

			return false;

	return true;

}

ll sum(point k)

{

	memset(val,0,sizeof(val));

	if(!in(k))return 0;

	for(int i = 1;i <= m;++i)

	{

		if(sign(cross(p[v[i]] - p[u[i]],k - p[u[i]])) < 0)

		{

			val[1] += c[i];

			val[u[i]] -= c[i];

			val[v[i]] += c[i];

		}

		else

		{

			val[u[i]] += c[i];

			val[v[i]] -= c[i];

		}

	}

	ll ans = INF;

	for(int i = 1;i <= n;++i)val[i] += val[i - 1],ans = min(ans,val[i]);

	return ans;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)p[i].x = read(),p[i].y = read();

	p[n + 1] = p[1];

	for(int i = 1;i <= n;++i)l[i] = line(p[i],p[i + 1] - p[i]);

	for(int i = 1;i <= m;++i)

	{

		u[i] = read();v[i] = read();c[i] = read();

		if(u[i] > v[i])swap(u[i],v[i]);

	}

	s.x = (double)read();s.y = (double)read();

	t.x = (double)read();t.y = (double)read();

	ll ans = sum(s) + sum(t);

	memset(val,0,sizeof(val));

	ll res = 0;

	for(int i = 1;i <= m;++i)

	{

		if(sign(cross(p[v[i]] - p[u[i]],p[v[i]] - s)) !=  sign(cross(p[v[i]] - p[u[i]],p[v[i]] - t)))

		{

			res += c[i];

		}

	}

	cout << min(ans,res) << endl;

	return 0;

}