{"trustable":false,"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":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Long times ago, there are beautiful historic walls in the city. These walls divide the city into many parts of area. \n \u003cbr\u003e \n \u003cbr\u003eSince it was not convenient, the new king wants to destroy some of these walls, so he can arrive anywhere from his castle. We assume that his castle locates at $(0.6*\\sqrt 2 , 0.6*\\sqrt 3 )$. \n \u003cbr\u003e \n \u003cbr\u003eThere are $n$ towers in the city, which numbered from 1 to n. The ith\u0027s location is $(x_i,y_i)$. Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower $u_i$ and the tower $v_i$(including the endpoint). The cost of destroying the ith wall is $w_i$. \n \u003cbr\u003e \n \u003cbr\u003eNow the king asks you to help him to divide the city. Firstly, the king wants to destroy as less walls as possible, and in addition, he wants to make the cost least. \n \u003cbr\u003e \n \u003cbr\u003eThe walls only intersect at the endpoint. It is guaranteed that no walls connects the same tower and no 2 walls connects the same pair of towers. Thait is to say, the given graph formed by the walls and towers doesn\u0027t contain any multiple edges or self-loops. \n \u003cbr\u003e \n \u003cbr\u003eInitially, you should tell the king how many walls he should destroy at least to achieve his goal, and the minimal cost under this condition. \n \u003cbr\u003e \n\u003c/div\u003e\n国王的领土被分割成n个地方,国王想到达他领土的每一个地方,但是现在一些有一些城墙的隔绝两个地方,拆掉城墙需要耗费 一些财力物力,国王想拆最小的城墙数,花费最小的人力物力。给出的数据 ,开始给出的n个坐标值,(这个是唬人的,一点用都没有),而后给出 u v w表示一个城墙连接的两个地方和拆掉需要耗费的代价了。"}},{"title":"Input","value":{"format":"HTML","content":"There are several test cases. \n\u003cbr\u003e \n\u003cbr\u003eFor each test case: \n\u003cbr\u003e \n\u003cbr\u003eThe first line contains 2 integer n, m. \n\u003cbr\u003e \n\u003cbr\u003eThen next n lines describe the coordinates of the points. \n\u003cbr\u003e \n\u003cbr\u003eEach line contains 2 integers $x_i,y_i$. \n\u003cbr\u003e \n\u003cbr\u003eThen m lines follow, the ith line contains 3 integers $u_i,v_i,w_i$ \n\u003cbr\u003e \n\u003cbr\u003e$|x_i|,|y_i|\\le 10^5$ \n\u003cbr\u003e \n\u003cbr\u003e$3\\le n \\le 100000,1\\le m \\le 200000$ \n\u003cbr\u003e \n\u003cbr\u003e$1\\le u_i,v_i\\le n ,u_i\\ne v_i ,0\\le w_i \\le 10000$ \n\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case outout one line with 2 integers sperate by a space, indicate how many walls the king should destroy at least to achieve his goal, and the minimal cost under this condition. \n\u003cbr\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e4 4\n-1 -1\n-1 1\n1 1\n1 -1\n1 2 1\n2 3 2\n3 4 1\n4 1 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1 1\u003c/pre\u003e"}}]}