5662번 - Highway Patrol 다국어

문제

Crimes in city of Megacity are going high. To fight the crimes, the authorities have created a highway patrol. The city consists of a number of one-way roads. At the ends of each road, there is a base station for the patrol troops. Each base station has a number of troops. At the beginning, each station sends a troop along all the outgoing highways from that station. The troop patrols the highway and whenever it reaches the station on the other side of the highway, it waits there, and the troop that has been waiting there the most, is sent along the highway that has not been patrolled the longest time.

Soon, they faced some difficulties, cause, the frequency of patrolling a highway is more and more dependent on the number of highways that started and ended at the base station. If the number of highways started at a base station is more than the number of highways ended there, the roads are patrolled less frequently. And if, no highways end at some base station, then, the highways started from there, will not be patrolled more than once.

In this situation, the highway patrol decided to remove some highways from the patrolling schedule, so that, at each base station, the number of highways started and ended at any base station will be equal. The rest of the highways will be monitored using video surveillance. But, due to some security issues, there are some highways that have to be patrolled.

Now, given the cost of patrolling highways, and that of installing video surveillance, find the minimum cost of monitoring the whole city. Please keep in mind that, video surveillance can not substitute the highway patrol completely. So, there has to be at least one highway that will be patrolled.

입력

First line of the input contains an integer T(T≤ 70), the number of test cases. This is followed by T test cases. Each test case starts with two integers N(1 ≤ N ≤ 100) and M(1 ≤ M ≤ 1000), the number of base stations and highways. This is followed by M lines, each containing 5 integers, u, v, p, s, x(1 ≤ u,v ≤ N, 0 ≤ p, s ≤ 1000000) where u and v means, the highway starts from base station u, and ends at v, p is the cost of patrolling and s is the cost of installing video surveillance. If the highway must be patrolled, then x will be one. Otherwise it will be zero.

출력

For each test case, output the case number, followed by the minimum cost to monitor the highways. If it is not possible to patrol satisfying the given constraints, output “impossible” (without quotes).

제한

힌트