Правитель Байтландии недавно решил проехать по всем городам своей огромной страны, чтобы посмотреть, как развиваются самые удаленные ее районы. Последняя его поездка была достаточно давно, и за это время система городов и дорог существенно изменилась. Байтландия представляет собой N городов, некоторые из которых соединены дорогами, M из которых принадлежат государству, а K дорог находятся в частных владениях. По всем дорогам Байтландии можно перемещаться в обоих направлениях. Кроме того любую пару городов напрямую может соединять не более одной дороги. Известно, что в Байтландии существует путь между любыми двумя городами, причем вполне возможно, что этот путь может содержать как государственные дороги, так и частные. Правитель хочет проезжать только по государственным дорогам. В связи с этим, министры Байтландии решили пообщаться с владельцами частных дорог, и выяснили, за какую цену можно купить каждую из них. Кроме этого они понимают, что некоторые государственные дороги могут оказаться невостребованными в поездке, поэтому их можно сначала продать, а потом вырученные деньги потратить на покупку частных дорог, дабы не разорять государственную казну.
Для организации поездки требуется построить такую систему дорог Байтландии, чтобы было возможно посетить все города (возможно, некоторые из них по несколько раз из-за сложившихся дорожных обстоятельств), при этом потратив как можно меньше денег из государственной казны. Если некоторые из государственных дорог будут проданы, то вырученные деньги будут использоваться в первую очередь, если же этих денег не хватит, недостающие деньги будут взяты из казны. Оставшиеся от продажи дорог деньги в казну не возвращаются. Система городов и дорог достаточно сложная, поэтому для создания оптимального плана действий организаторы обратились к Вам – лучшему программисту Байтландии. Теперь Вам нужно разработать программу, которая по заданной системе городов и дорог определит минимальные затраты из государственной казны для того, чтобы система дорог позволила осуществить поездку правителя Байтландии по всем городам.