//http://www.renfei.org/blog/isap.html 带解释的

//https://www.cnblogs.com/bosswnx/p/10353301.html 形式和我的比较相近的

#include<queue>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxe 400096  //pay  双向边 一共10万条路 双向就是20万 反边就是40万

#define maxv 100005    //pay

#define maxn 55    //pay

#define sc scanf

#define pt printf

#define rep(i,a,b)  for(int i=(a);i<(b);++i)

const int inf = 0x3f3f3f3f;

int cg,sp,ins;  //cg change sp是总流量 ins是加速回溯点

int T,N,M ,s,t;

int q[maxv],fro,rea;

typedef struct ed{

    int v,nxt,cap; //dis

}ed;

ed e[maxe];

int who_is_westernest,who_is_easternest,wx,ex;

int tot,head[maxv],cur[maxv],vis[maxv],bk[maxv],d[maxv],num[maxv]; //

int mi(int a,int b) {return a<b?a:b;}

int mx(int a,int b) {return a>b?a:b;}

void add(int u,int v,int cap)

{

    e[tot].v=v;         e[tot].nxt=head[u];

    /*e[tot].dis=dis;*/     e[tot].cap=cap;

    head[u]=tot++;

    e[tot].v=u;         e[tot].nxt=head[v];

    /*e[tot].dis=-dis;*/    e[tot].cap=;

    head[v]=tot++;

}

// 仅有一次的BFS为ISAP节省了不少时间

bool bfs()

{

    //数组模拟queue

    memset(vis, , sizeof(vis));

    fro = rea = ;

    q[rea] = t; ++rea;

    vis[t] = ;

    d[t] = ;

    int u,v,i;

    while (rea>fro)

    {

        u = q[fro]; ++fro;

        for (i=head[u]; i!=-; i=e[i].nxt)

        {

            v=e[i].v;

            if (!vis[v] && e[i^].cap )

            {

                vis[v] = true;

                d[v] = d[u] + ;

                q[rea] = v; ++rea;

            }

        }

    }

    return vis[s];

}

// 增广

int augment()

{

    int  flow = inf, i;

    cg = t;

    // 从汇点到源点通过 p 追踪增广路径, flow 为一路上最小的残量

    while (cg != s) {

        i = bk[cg];

        if(flow>=e[i].cap)

        {

            flow = e[i].cap;

            ins = e[i^].v;

            //用来加速寻找，在最小流量断开的地方重新开始寻找

            //嗯，等一下 我这个是从终点往起点寻找，而确定增光路径是从起点到终点

            //那么起点是河流的上游，那么回溯的河段应该尽可能的往上游靠近

            //所以应该将flow>e[i].cap的大于号改成大于等于号

        }

        cg = e[i^].v;

    }

    cg = t;

    // 从汇点到源点更新流量

    while (cg != s) {

        i = bk[cg];

        e[i].cap -= flow;

        e[i^].cap += flow;

        cg = e[i^].v;

    }

    return flow;

}

//由于每次修改层次的时候，都是在到剩下子节点的距离中挑选最短的加1 所以层次分明不会出现死循环

int max_flow()

{

    int flow = ,i,u,v;

    bool advanced;

    if(bfs()==false) return ;

    memset(num, , sizeof(num));

    for (i = ; i <= N; ++i) ++num[d[i]];

    //不是从s到t，你要知道统计每个层次的点的个数是全局统计的

    u = s;

    memcpy(cur, head, sizeof(head));

    while (d[s] < N)

    //终点是0，那么起点所在层次最多是N-1 同理，不是d[s]<t

    {

        if (u == t)

        {

            flow += augment();

            u = ins;    //pay speed up

        }

        advanced = false;

        for (i = cur[u]; i!=-; i=e[i].nxt)

        {

            v = e[i].v;

            if (e[i].cap && d[u] == d[v] + )

            {

                advanced = true;

                bk[v] = i;

                cur[u] = i;

                u = v;

                break;

            }

        }

        if (!advanced)

        { // retreat

            int m = N;

            for (i = head[u]; i != -; i=e[i].nxt)

            {

                if (e[i].cap&&m>d[e[i].v])

                {

                    cur[u] = i;

                    m = d[e[i].v];

                }

            }

            if (--num[d[u]] == ) break; // gap 优化

            ++num[d[u] = m+];

            //我以前一直在想 如果没有找到怎么办呢 现在发现原来找不到的话距离会被赋成N+1

            if (u != s)

                u = e[bk[u]^].v;

        }

    }

    return flow;

}

void init()

{

    tot=; wx= inf,ex=-inf;

    memset(head,-,sizeof(head));   //pay

}

int main()

{

    freopen("in.txt","r",stdin);

    d[]=; bk[]=-;

    sc("%d",&T);

    while(T--)

    {

        sc("%d%d",&N,&M);

        sp = ;

        int i,u,v,w,x,y;

        init();

        for(i=;i<=N;++i)

        {

            sc("%d%d",&x,&y);

            if(x<wx) wx=x,who_is_westernest=i;

            if(x>ex) ex=x,who_is_easternest=i;

        }

        s=who_is_westernest,t=who_is_easternest;

        for(i=;i<=M;++i) sc("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);

        sp = max_flow();

        pt("%d\n",sp);

    }

    return ;

}