Description

在遥远的辽阔海域有许多岛，岛上的所 有交通都依靠船只。每条路线都是连接两个不同岛屿的直线，并且是双 向的。在一个小时内，一条航线可以向一个方向运送一定数量的旅客。 除出发岛和到达岛外，没有两条路线交叉或重叠。每个岛都可被视为$XY$ 平面坐标系上的一个点。$X$ 坐标由西向东递增，$Y$ 坐标由南向北递增。 有许多旅客都从最西端的岛出发，希望到达最东端的岛，计算每个小时 到达最东端的岛的旅客最大数量（运输力）。

Format

Input

第1行包含一个整数$T （1≤T ≤20）$，即测试用例的数 量。每个测试用例的第1行都包含两个整数$N$ 和$M$ （$2≤N ，M≤100000）$，表示岛屿数和航线数。岛屿编号为$1～N$ 。接下来的$N$ 行，每行都包含两个整数，即一个岛的$X$ 和$Y$ 坐标。$N$ 行中的第$K$ 行表 示$K$ 岛，所有坐标的绝对值都不超过$100000$。再接下来有$M$ 行，每行都 包含三个整数$I_1 、I_2 （1≤I_1 、I_2 ≤N ）$和$C （1≤C ≤10000）$，表 示有一条连接$I_1$ 岛和$I_2$岛的航线，可以在一小时内单向运送$C$ 名乘 客。最西边只有一个岛，最东边只有一个岛。没有两个岛屿有相同的坐 标。每个岛都可以按航线去任何其他岛。

Output

对每个测试用例，都在一行中输出一个整数，即运输力。

Samples

1
5 7
3 3
3 0
3 1
0 0
4 5
1 3 3
2 3 4
2 4 3
1 5 6
4 5 3
1 4 4
3 4 2

9