{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"В эпоху телевидения не так много людей посещают театральные представления. Древние комики Малидезии осведомлены об этом факте. Они хотят распространить театр и, прежде всего, древние комедии. Они напечатали пригласительные карточки со всей необходимой информацией и программой. Много студентов было нанято для распространения этих приглашений среди людей. Каждому студенческому волонтеру была назначена ровно одна автобусная остановка, и он или она оставался там весь день, раздавая приглашения пассажирам, путешествующим на автобусе. Был проведен специальный курс, где студенты учились влиять на людей и различать влияние от грабежа. \r\u003cbr\u003e\r\u003cbr\u003eТранспортная система очень особенная: все маршруты однонаправленные и соединяют ровно две остановки. Автобусы отправляются с оригинальной остановки с пассажирами каждые полчаса. Доходя до конечной остановки, они возвращаются обратно на оригинальную остановку, где ждут до следующего полного часа, например, X:00 или X:30, где \u0027X\u0027 обозначает час. Плата за проезд между двумя остановками указана в специальных таблицах и оплачивается на месте. Маршруты спланированы таким образом, что каждая круговая поездка (т.е. путешествие, начинающееся и заканчивающееся на одной и той же остановке) проходит через Центральную Контрольную Остановку (ЦКО), где каждый пассажир должен пройти тщательную проверку, включая сканирование тела. \r\u003cbr\u003e\r\u003cbr\u003eВсе студенты ACM покидают ЦКО каждое утро. Каждый волонтер должен переместиться на одну заранее определенную остановку, чтобы пригласить пассажиров. Волонтеров столько же, сколько и остановок. В конце дня все студенты возвращаются в ЦКО. Вам нужно написать компьютерную программу, которая поможет ACM минимизировать сумму денег, которую им нужно платить каждый день за транспорт своих сотрудников. \r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Ввод состоит из N случаев. Первая строка ввода содержит только положительное целое число N. Затем следуют случаи. Каждый случай начинается с строки, содержащей ровно два целых числа P и Q, 1 \u0026lt;\u003d P,Q \u0026lt;\u003d 1000000. P - количество остановок, включая ЦКО, и Q - количество автобусных линий. Затем идут Q строк, каждая описывающая одну автобусную линию. Каждая из строк содержит ровно три числа - оригинальную остановку, конечную остановку и цену. ЦКО обозначается числом 1. Цены - положительные целые числа, сумма которых меньше 1000000000. Можно также предположить, что всегда можно добраться от любой остановки до любой другой остановки."}},{"title":"Output","value":{"format":"HTML","content":"Для каждого случая выведите одну строку, содержащую минимальную сумму денег, которую ACM должна платить каждый день за транспорт своих волонтеров."}},{"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\u003e2\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\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e46\r\n210\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}