Дорожный патруль
Преступность в городе Мегаполис растет. Чтобы бороться с ней, власти создали дорожный патруль. Город состоит из сети односторонних дорог, на концах которых расположены базовые станции для патрульных войск. Каждая станция имеет определенное количество войск. В начале каждая станция отправляет войска по всем исходящим от нее шоссе. Войска патрулируют шоссе и, достигнув станции на другом конце, остаются там, а войска, которые ждали дольше всего, отправляются по шоссе, которое не патрулировалось дольше всего.
Однако вскоре возникли трудности: частота патрулирования шоссе стала зависеть от количества шоссе, начинающихся и заканчивающихся на базовой станции. Если количество шоссе, начинающихся на станции, превышает количество шоссе, заканчивающихся там, дороги патрулируются реже. Если ни одно шоссе не заканчивается на какой-то станции, то шоссе, начинающиеся оттуда, не будут патрулироваться более одного раза.
В этой ситуации дорожный патруль решил исключить некоторые шоссе из графика патрулирования, чтобы на каждой базовой станции количество шоссе, начинающихся и заканчивающихся на ней, было одинаковым. Остальные шоссе будут контролироваться с помощью видеонаблюдения. Однако из-за проблем с безопасностью есть шоссе, которые обязательно должны патрулироваться.
Теперь, учитывая стоимость патрулирования шоссе и установки видеонаблюдения, найдите минимальную стоимость мониторинга всего города. Помните, что видеонаблюдение не может полностью заменить дорожный патруль, поэтому должно быть хотя бы одно шоссе, которое будет патрулироваться.
Входные данные
Первая строка входных данных содержит целое число T (T ≤ 70), количество тестов. Далее следуют T тестов. Каждый тест начинается с двух целых чисел N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 1000), количество базовых станций и шоссе. Далее следуют M строк, каждая из которых содержит 5 целых чисел: u, v, p, s, x (1 ≤ u, v ≤ N, 0 ≤ p, s ≤ 1000000), где u и v обозначают, что шоссе начинается от базовой станции u и заканчивается на v, p — это стоимость патрулирования, а s — стоимость установки видеонаблюдения. Если шоссе должно патрулироваться, то x будет равно единице. В противном случае оно будет равно нулю.
Выходные данные
Для каждого теста выведите номер случая, за которым следует минимальная стоимость мониторинга шоссе. Если невозможно организовать патрулирование, удовлетворяя заданным ограничениям, выведите "impossible" (без кавычек).