{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAlex is a system administrator of \u003ci\u003eDomestic Networks Inc.\u003c/i\u003e His network connects apartments and spans over multiple buildings.\u003c/p\u003e\u003cp\u003eThe network expands and Alex has to design a new network segment. He has a map that shows apartments to connect and possible links. Each link connects two apartments and for each possible link its length is known. The goal is to make all apartments connected (possibly through other apartments).\u003c/p\u003e\u003cp\u003e\u003ci\u003eDomestic Networks Inc.\u003c/i\u003e buys cable in the nearest cable shop. Unfortunately, shop sells only category 5 and 6 cables at price of \u003ci\u003ep\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e and \u003ci\u003ep\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e rubles per meter respectively. Moreover, there are only \u003ci\u003eq\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e meters of category 5 cable and \u003ci\u003eq\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e meters of category 6 cable available in the shop.\u003c/p\u003e\u003cp\u003eHelp Alex to solve a hard problem: make a new network construction plan with possible minimal cost. A plan consists of list of links to be made and cable category for each link (each link should be a single piece of cable of either 5 or 6 category). The cost of the plan is the sum of cost of all cables. The total length of cables of each category used in the plan should not exceed the quantity of the cable available in the shop.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input file contains two numbers: \u003ci\u003en\u003c/i\u003e — the number of apartments to be connected and \u003ci\u003em\u003c/i\u003e — the number of possible links (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1000, 1 ≤ \u003ci\u003em\u003c/i\u003e ≤ \u003cnobr\u003e10 000\u003c/nobr\u003e).\u003c/p\u003e\u003cp\u003eFollowing \u003ci\u003em\u003c/i\u003e lines contain possible link descriptions. Each description consists of three integer numbers: \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — apartments that can be connected by the link and \u003ci\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — link length in meters (0 ≤ \u003ci\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ 100). Apartments are numbered from 1 to \u003ci\u003en\u003c/i\u003e.\u003c/p\u003e\u003cp\u003eThe last line of the input file contains four integer numbers: \u003ci\u003ep\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e, \u003ci\u003eq\u003c/i\u003e\u003csub\u003e5\u003c/sub\u003e, \u003ci\u003ep\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e and \u003ci\u003eq\u003c/i\u003e\u003csub\u003e6\u003c/sub\u003e — price and quantity of category 5 and 6 cables respectively (1 ≤ \u003ci\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e, \u003ci\u003eq\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e ≤ \u003cnobr\u003e10 000\u003c/nobr\u003e).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIf all apartments can be connected with the available cable, output \u003ci\u003en\u003c/i\u003e lines — an optimal network construction plan. The first line of the plan must contain plan’s cost. Other lines of the plan must consist of two integer numbers each: \u003ci\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — number of the link to make and \u003ci\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e — the category of the cable to make it of. Links are numbered from 1 to \u003ci\u003em\u003c/i\u003e in the order they are specified in the input file. If there are more than one optimal plans, output any of them.\u003c/p\u003e\u003cp\u003eIf there is no plan meeting all requirements, output a single word “\u003ctt\u003eImpossible\u003c/tt\u003e”.\u003c/p\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\u003e6 7\r\n1 2 7\r\n2 6 5\r\n1 4 8\r\n2 3 5\r\n3 4 5\r\n5 6 6\r\n3 5 3\r\n2 11 3 100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e65\r\n1 5\r\n2 6\r\n4 6\r\n5 6\r\n7 5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}