{"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\"\u003e 在遥远的广阔海域中,有许多岛屿。岛上居民生活,岛与岛之间的交通都依赖船只。\u003cbr\u003e 你在那里有一家运输公司。为乘客开通了一些航线。每条航线是连接两个不同岛屿的直线,是双向的。在一个小时内,一条航线可以在一个方向上运送一定数量的乘客。为了安全起见,没有两条航线会相交或重叠,也不会经过除出发岛屿和到达岛屿外的其他岛屿。每个岛屿可以被视为XY平面坐标系上的一个点。X坐标从西向东增加,Y坐标从南向北增加。\u003cbr\u003e 运输能力对你很重要。假设许多乘客从最西边的岛屿出发,想要到达最东边的岛屿,那么每小时到达后者的最大乘客数就是运输能力。请计算它。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":" 第一行包含一个整数T (1\u0026lt;\u003dT\u0026lt;\u003d20),表示测试用例的数量。\u003cbr\u003e 接下来是T个测试用例。每个测试用例的第一行包含两个整数N和M (2\u0026lt;\u003dN,M\u0026lt;\u003d100000),表示岛屿数量和航线数量。岛屿从1到N编号。\u003cbr\u003e 接下来是N行。每行包含两个整数,表示一个岛屿的X和Y坐标。第K行描述第K个岛屿。所有坐标的绝对值不超过100000。\u003cbr\u003e 然后是M行。每行包含三个整数I1, I2 (1\u0026lt;\u003dI1,I2\u0026lt;\u003dN) 和 C (1\u0026lt;\u003dC\u0026lt;\u003d10000)。表示有一条连接岛屿I1和岛屿I2的航线,每小时可以运送C名乘客。\u003cbr\u003e 保证航线遵守上述规则。只有一个岛屿是最西边的,只有一个岛屿是最东边的。没有两个岛屿会有相同的坐标。每个岛屿都可以通过航线到达任何其他岛屿。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":" 对于每个测试用例,输出一个整数,表示运输能力。\u003cbr\u003e"}},{"title":"示例","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\n5 7\r\n3 3\r\n3 0\r\n3 1\r\n0 0\r\n4 5\r\n1 3 3\r\n2 3 4\r\n2 4 3\r\n1 5 6\r\n4 5 3\r\n1 4 4\r\n3 4 2\r\n6 7\r\n-1 -1\r\n0 1\r\n0 2\r\n1 0\r\n1 1\r\n2 3\r\n1 2 1\r\n2 3 6\r\n4 5 5\r\n5 6 3\r\n1 4 6\r\n2 5 5\r\n3 6 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}