{"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\"\u003eMr. Panda lives in Pandaland. There are many cities in Pandaland. Each city can be treated as a point on a 2D plane. Different cities are located in different locations.\u003cbr\u003eThere are also M bidirectional roads connecting those cities. There is no intersection between two distinct roads except their endpoints. Besides, each road has a cost w.\u003cbr\u003eOne day, Mr. Panda wants to find a simple cycle with minmal cost in the Pandaland. To clarify, a simple cycle is a path which starts and ends on the same city and visits each road at most once.\u003cbr\u003eThe cost of a cycle is the sum of the costs of all the roads it contains.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, T. T test cases follow.\u003cbr\u003eEach test case begins with an integer M.\u003cbr\u003eFollowing M lines discribes roads in Pandaland.\u003cbr\u003eEach line has 5 integers $x_1, y_1, x_2, y_2,$ w, representing there is a road with cost w connecting the cities on $(x_1, y_1)$ and $(x_2, y_2).$\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the cost Mr. Panda wants to know.\u003cbr\u003eIf there is no cycles in the map, y is 0.\u003cbr\u003e\u003ch2\u003elimits\u003c/h2\u003e\u003cbr\u003e$\\bullet 1 ≤ T ≤ 50.$\u003cbr\u003e$\\bullet 1 ≤ m ≤ 4000.$\u003cbr\u003e$\\bullet -10000 ≤ x_i , y_i ≤ 10000.$\u003cbr\u003e$\\bullet 1 ≤ w ≤ 10^5.$\u003cbr\u003e"}},{"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\n5\r\n0 0 0 1 2\r\n0 0 1 0 2\r\n0 1 1 1 2\r\n1 0 1 1 2\r\n1 0 0 1 5\r\n9\r\n1 1 3 1 1\r\n1 1 1 3 2\r\n3 1 3 3 2\r\n1 3 3 3 1\r\n1 1 2 2 2\r\n2 2 3 3 3\r\n3 1 2 2 1\r\n2 2 1 3 2\r\n4 1 5 1 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 8\r\nCase #2: 4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}