{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe 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.\u003cbr\u003e\u003cbr\u003eThe 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.\u003cbr\u003e\u003cbr\u003eThe 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. \u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer $T$ ($1 \\leq T \\leq 1\\,000$), the number of test cases. For each test case:\u003cbr\u003e\u003cbr\u003eThe 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.\u003cbr\u003e\u003cbr\u003eIn 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.\u003cbr\u003e\u003cbr\u003eEach of the next $m$ lines contains two integers $u_i$ and $v_i$ ($1 \\leq u_i, v_i \\leq n$, $x_{u_i} \u0026lt; 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.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that the sum of all $n$ is at most $1\\,500\\,000$."}},{"title":"Output","value":{"format":"HTML","content":"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."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n6 6\r\n0 1 1\r\n2 2 1\r\n1 0 1\r\n1 2 1\r\n2 0 1\r\n3 1 1\r\n1 4\r\n3 5\r\n2 6\r\n5 6\r\n1 3\r\n4 2\r\n2 1\r\n0 0 8\r\n1 1 9\r\n1 2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 3\r\n9\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}