{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAs more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.\u003c/p\u003e\u003cp\u003eThe routine consists of \u003ci\u003eN\u003c/i\u003e modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let\u0027s define them as \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e. Meanwhile, \u003ci\u003eM\u003c/i\u003e pairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThere are two integers in the first line of input data, \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e (1 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 20000, 1 ≤ \u003ci\u003eM\u003c/i\u003e ≤ 200000) .\u003cbr\u003eThe next \u003ci\u003eN\u003c/i\u003e lines, each contains two integer, \u003ci\u003eA\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e and \u003ci\u003eB\u003csub\u003ei\u003c/sub\u003e\u003c/i\u003e.\u003cbr\u003eIn the following \u003ci\u003eM\u003c/i\u003e lines, each contains three integers: \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e, \u003ci\u003ew\u003c/i\u003e. The meaning is that if module \u003ci\u003ea\u003c/i\u003e and module \u003ci\u003eb\u003c/i\u003e don\u0027t execute on the same core, you should pay extra \u003ci\u003ew\u003c/i\u003e dollars for the data-exchange between them.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput only one integer, the minimum total cost.\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\u003e3 1\r\n1 10\r\n2 10\r\n10 3\r\n2 3 1000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e13\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}