{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eIn the age of television, not many people attend theater\r\nperformances. Antique Comedians of Malidinesia are aware of this fact. They\r\nwant to propagate theater and, most of all, Antique Comedies. They have\r\nprinted invitation cards with all the necessary information and with the\r\nprogramme. A lot of students were hired to distribute these invitations\r\namong the people. Each student volunteer has assigned exactly one bus stop\r\nand he or she stays there the whole day and gives invitation to people\r\ntravelling by bus. A special course was taken where students learned\r\nhow to influence people and what is the difference between influencing\r\nand robbery.\r\n\r\n\u003c/p\u003e\u003cp\u003eThe transport system is very special: all lines are\r\nunidirectional and connect exactly two stops. Buses leave\r\nthe originating stop with passengers each half an hour. After reaching\r\nthe destination stop they return empty to the originating stop,\r\nwhere they wait until the next full half an hour, e.g. X:00 or\r\nX:30, where \u0027X\u0027 denotes the hour. The fee for transport between two\r\nstops is given by special tables and is payable on the spot. The\r\nlines are planned in such a way, that each round trip (i.e. a journey\r\nstarting and finishing at the same stop) passes through a \u003ci\u003eCentral\r\nCheckpoint Stop\u003c/i\u003e (CCS) where each passenger has to pass a thorough\r\ncheck including body scan.\r\n\r\n\u003c/p\u003e\u003cp\u003eAll the ACM student members leave the CCS each morning. Each volunteer is\r\nto move to one predetermined stop to invite passengers. There are as many\r\nvolunteers as stops. At the end of the day, all students travel back to CCS.\r\nYou are to write a computer program that helps ACM to minimize the amount of\r\nmoney to pay every day for the transport of their employees.\r\n\r\n\r\n\u003c/p\u003e\u003ch3\u003eInput\u003c/h3\u003e\r\n\r\n\u003cp\u003eThe input consists of \u003cvar\u003eN\u003c/var\u003e cases. The first line of the input\r\ncontains only positive integer \u003cvar\u003eN\u003c/var\u003e. Then follow the cases.\r\nEach case begins with a line containing exactly two integers\r\n\u003cvar\u003eP\u003c/var\u003e and \u003cvar\u003eQ\u003c/var\u003e, \u003cvar\u003e1 \u0026lt;\u003d P,Q \u0026lt;\u003d 1000000\u003c/var\u003e.\r\n\u003cvar\u003eP\u003c/var\u003e is the number of stops including CCS and \u003cvar\u003eQ\u003c/var\u003e the\r\nnumber of bus lines. Then there are \u003cvar\u003eQ\u003c/var\u003e lines, each describing one\r\nbus line. Each of the lines contains exactly three numbers - the originating\r\nstop, the destination stop and the price. The CCS is designated by\r\nnumber \u003cvar\u003e1\u003c/var\u003e. Prices are positive integers the sum of which is\r\nsmaller than \u003cvar\u003e1000000000\u003c/var\u003e. You can also assume it is always\r\npossible to get from any stop to any other stop.\r\n\r\n\r\n\u003c/p\u003e\u003ch3\u003eOutput\u003c/h3\u003e\r\n\r\n\u003cp\u003eFor each case, print one line containing the minimum amount of\r\nmoney to be paid each day by ACM for the travel costs of its volunteers.\r\n\r\n\r\n\u003c/p\u003e\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\r\nSample input:\r\n2\r\n2 2\r\n1 2 13\r\n2 1 33\r\n4 6\r\n1 2 10\r\n2 1 60\r\n1 3 20\r\n3 4 10\r\n2 4 5\r\n4 1 50\r\n\r\nSample output:\r\n46\r\n210\r\n\u003c/pre\u003e\r\n\u003cb\u003eWarning: large Input/Output data, be careful with certain languages\u003c/b\u003e\n\u003c/div\u003e"}}]}