{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eAn oligarch Vovan, as many other oligarchs, transports oil from West Cuckooland \r\nto East Cuckooland. He owns a huge oil-producing station in West Cuckooland, \r\nan equally huge oil-refining station in East Cuckooland and a system of oil \r\npipelines to move oil from one country to another. Vovan has a map of these \r\npipelines on his table. He would like to know, how much oil this system can \r\ntransport.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEach pipeline connects some pair of stations. All stations on the map are numbered: the producing station has number 1, the refining one has number \u003ci\u003eN\u003c/i\u003e and the transit ones have numbers from 2 to \u003ci\u003eN\u003c/i\u003e\u0026nbsp;−\u0026nbsp;1, inclusive. Each pipeline can transport a limited quantity of oil, but in any direction. Vovan doesn\u0027t know that the Earth is round, so each station on his map has plane coordinates (\u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e are the coordinates of \u003ci\u003ei\u003c/i\u003e-th station). The pipelines are represented as line segments. Any pair of pipelines on the map can intersect only at endpoints. It is known, that the oil-producing station has the smallest \u003ci\u003ex\u003c/i\u003e-coordinate of all stations, and the oil-refining station has the largest \u003ci\u003ex\u003c/i\u003e-coordinate.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains an integer \u003ci\u003eN\u003c/i\u003e. 2\u0026nbsp;≤\u0026nbsp;\u003ci\u003eN\u003c/i\u003e\u0026nbsp;≤\u0026nbsp;10000. Next \u003ci\u003eN\u003c/i\u003e lines \r\ncontain the coordinates of the stations (\u003ci\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e,\u0026nbsp;\u003ci\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e) separated with a space. \r\nCoordinates are integers with absolute values no more than 10\u003csup\u003e8\u003c/sup\u003e. Next line \r\ncontains an integer \u003ci\u003eM\u003c/i\u003e\u0026nbsp;— the number of oil pipelines. Next \u003ci\u003eM\u003c/i\u003e lines contain specifications of pipelines: for each pipeline, the three numbers describe a pair of stations connected by it and its flow capacity\u0026nbsp;— an integer from 1 to 10\u003csup\u003e8\u003c/sup\u003e. It is guaranteed that Vovan\u0027s system can transport some positive quantity of oil, and can\u0027t transport more than 2·10\u003csup\u003e9\u003c/sup\u003e oil units.\r\n\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIn the first line output the maximal quantity of oil that the Vovan\u0027s system \r\ncan transport. In the following \u003ci\u003eM\u003c/i\u003e lines output the transportation plan\u0026nbsp;— triples of numbers (\u003ci\u003eA\u003c/i\u003e,\u0026nbsp;\u003ci\u003eB\u003c/i\u003e,\u0026nbsp;\u003ci\u003eC\u003c/i\u003e), denoting that \u003ci\u003eC\u003c/i\u003e oil units should flow from station \u003ci\u003eA\u003c/i\u003e to station \u003ci\u003eB\u003c/i\u003e. All pipelines should be presented exactly once in this list (even those, in which the oil flow is equal to zero). The values of \u003ci\u003eC\u003c/i\u003e should always be non-negative.\u003c/div\u003e\u003c/div\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\u003e3\r\n0 0\r\n1 1\r\n2 0\r\n2\r\n1 2 2\r\n2 3 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1 2 1\r\n2 3 1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}