Crossfire
题号：NC17357
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

    袋鼠先生在玩一个塔防游戏。这个游戏中，一共有n个防御塔，第i个塔位于(xi,yi)的位置，这n个防御塔形成了一个严格的凸多边形。有m道防御网，你可以把第i道防御网看做连接第ui个防御塔和第vi个防御塔的一条线段，穿越它就需要消耗ci的血量。
    袋鼠先生想从(sx,sy)位置走到(tx,ty)位置，他想知道最少要消耗多少血量。

输入描述:

第一行两个整数n, m(1≤n,m≤100,000)。接下来n行，每行包含两个整数xi,yi(|xi|,|yi|≤1,000,000,000)，表示防御塔的位置，保证防御塔形成了一个严格的凸多边形，即没有三点共线，并且按逆时针顺序给出。接下来m行，每行三个整数ui,vi,ci(1≤ui,vi≤n, ui≠vi, 1≤ci≤1,000,000,000)，表示每个防御网的参数。
然后接下来两行每行两个整数sx,sy和tx,ty (|sx|,|sy|,|tx|,|ty|≤1,000,000,000)，保证起点和终点都不在防御网上。

输出描述:

输出最少消耗的血量。
示例1

输入

复制 
4 6
0 0
4 0
4 4
0 4
1 2 2
2 3 2
3 4 2
4 1 2
1 3 3
2 4 3
2 1
2 3

输出

复制 
4
示例2

输入

复制 
4 6
0 0
4 0
4 4
0 4
1 2 2
2 3 2
3 4 2
4 1 2
1 3 3
2 4 3
2 1
1 2

输出

复制 
3

说明

黑色表示代价为2的边，红色表示代价为3的边。
从S走到T1可以先往外走，然后从外面绕圈，然后进入T1，代价为4。
从S走到T2可以直接走，代价为3。