{"trustable":false,"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 \u003cp\u003eIn this era dominated by television, theater attendance has significantly declined. The Antique Comedians of Malidinesia are fully cognizant of this trend and aim to promote both the art of theater and, more specifically, Antique Comedies. To achieve this goal, they have produced invitation cards containing all the essential details and the program schedule. Numerous students have been recruited to disseminate these invitations to the public. Each student volunteer is responsible for a designated bus stop, where they remain throughout the day, distributing invitations to bus passengers. These students have undergone a specialized course to learn effective persuasion techniques, distinguishing them from unlawful activities such as robbery.\u003c/p\u003e\n \u003cp\u003eThe transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passengers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where \u0027X\u0027 denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a \u003ci\u003eCentral Checkpoint Stop\u003c/i\u003e (CCS) where each passenger has to pass a thorough check including body scan.\u003c/p\u003e\n \u003cp\u003eAll the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.\u003c/p\u003e\n \u003ch3\u003eInput\u003c/h3\u003e\n \u003cp\u003eThe input consists of \u003cvar\u003eN\u003c/var\u003e cases. The first line of the input contains only positive integer \u003cvar\u003eN\u003c/var\u003e. Then follow the cases. Each case begins with a line containing exactly two integers \u003cvar\u003eP\u003c/var\u003e and \u003cvar\u003eQ\u003c/var\u003e, \u003cvar\u003e1 \u0026lt;\u003d P,Q \u0026lt;\u003d 1000000\u003c/var\u003e. \u003cvar\u003eP\u003c/var\u003e is the number of stops including CCS and \u003cvar\u003eQ\u003c/var\u003e the number of bus lines. Then there are \u003cvar\u003eQ\u003c/var\u003e lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number \u003cvar\u003e1\u003c/var\u003e. Prices are positive integers the sum of which is smaller than \u003cvar\u003e1000000000\u003c/var\u003e. You can also assume it is always possible to get from any stop to any other stop.\u003c/p\u003e\n \u003ch3\u003eOutput\u003c/h3\u003e\n \u003cp\u003eFor each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.\u003c/p\u003e\n \u003ch3\u003eExample\u003c/h3\u003e\n \u003cpre\u003e\nSample input:\n2\n2 2\n1 2 13\n2 1 33\n4 6\n1 2 10\n2 1 60\n1 3 20\n3 4 10\n2 4 5\n4 1 50\n\nSample output:\n46\n210\n\u003c/pre\u003e\u003cb\u003eWarning: large Input/Output data, be careful with certain languages\u003c/b\u003e\n\u003c/div\u003e"}}]}