Description

The annual kart race will soon be held in Byteland. The map of the race consists of $n$ different intersections and $m$ one-way streets. These intersections are labeled from $1$ to $n$, the $i$-th of which is located at $(x_i,y_i)$. There are no cycles in the street network, one can only drive to some intersections with the strictly larger value of x-coordinate. The streets may only intersect at the intersections.

The race will start at the $1$-st intersection and will finish at the $n$-th intersection. The racers can pick their routes themselves, but they can only drive along the streets marked on the map. It is guaranteed that one can reach any place from $1$, and any place can reach $n$, so any route is valid.

The kart race attracts so many sponsors. Each intersection has a slot to set a banner, if you choose to set a banner at the $i$-th intersection, the race company will get $w_i$ profits. You are a middleman in the race company, your job is to choose some intersections to set banners such that the total profits are maximized. You know that no racer is willing to see more than a banner, so for every possible route from $1$ to $n$, you should guarantee that at most one intersection is chosen.

Format

Input

The first line contains a single integer $T$ ($1 \leq T \leq 1\,000$), the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 100\,000$, $1\leq m\leq 2n$), denoting the number of intersections and the number of one-way streets.

In the next $n$ lines, the $i$-th line contains three integers $x_i$, $y_i$ and $w_i$ ($0\leq x_i,y_i\leq 10^9$, $1\leq w_i\leq 10^9$), describing the $i$-th intersection. It is guaranteed that no two intersections share the same coordinator.

Each of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $x_{u_i} < x_{v_i}$), denoting a one way street from $u_i$ to $v_i$. It is guaranteed that each pair of $u_i$ and $v_i$ will be described at most once.

It is guaranteed that the sum of all $n$ is at most $1\,500\,000$.

Output

For each test case, print a single integer in the first line, denoting the maximum total profits. Then print a sequence of integers in the second line, denoting the indexes of intersections you choose to set a banner. If there are multiple optimal solutions, you should print the lexicographically smallest one.

Samples

2
6 6
0 1 1
2 2 1
1 0 1
1 2 1
2 0 1
3 1 1
1 4
3 5
2 6
5 6
1 3
4 2
2 1
0 0 8
1 1 9
1 2

2
2 3
9
2