고속도로 순찰

도시에는 $N$개의 기지국이 있고, 이들을 잇는 $M$개의 일방통행 고속도로가 있다. $i$번 고속도로는 기지국 $u_i$에서 출발하여 기지국 $v_i$에서 끝난다. 도시를 지키기 위해 모든 고속도로는 다음 두 방법 중 정확히 하나로 감시해야 한다.

• 순찰한다. 비용은 $p_i$이다.
• 영상 감시 장비를 설치한다. 비용은 $s_i$이다.

순찰 일정은 균형을 이루어야 한다. 즉, 모든 기지국에서 그 기지국을 출발하는 순찰 고속도로의 수와 그 기지국으로 들어오는 순찰 고속도로의 수가 같아야 한다. 다시 말해, 순찰하는 고속도로들의 집합은 순환(circulation)을 이루어야 하며, 각 기지국의 순찰 진출 차수와 진입 차수가 같아야 한다.

보안상의 이유로 반드시 순찰해야 하는 고속도로가 있다. $x_i = 1$이면 $i$번 고속도로는 반드시 순찰해야 하고, $x_i = 0$이면 두 방법 중 어느 것을 사용해도 된다.

영상 감시가 순찰을 완전히 대체할 수는 없으므로, 적어도 하나의 고속도로는 반드시 순찰해야 한다.

가능한 최소 총 감시 비용을 구하여라. 유효한 일정이 존재하지 않으면 그 사실을 보고하여라.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 70$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 기지국의 수 $N$과 고속도로의 수 $M$ ($1 \le N \le 100$, $1 \le M \le 1000$)이 주어진다. 이어지는 $M$개의 줄에는 각각 다섯 정수 $u$, $v$, $p$, $s$, $x$ ($1 \le u, v \le N$, $0 \le p, s \le 1000000$, $x \in \{0, 1\}$)가 주어진다. 이는 기지국 $u$에서 출발하여 기지국 $v$에서 끝나는 고속도로로, 순찰 비용은 $p$, 영상 감시 비용은 $s$이며, 반드시 순찰해야 하면 $x = 1$, 아니면 $x = 0$이다.

각 테스트 케이스마다 Case i: c 형식의 줄을 출력한다. 여기서 $i$는 테스트 케이스 번호($1$부터 시작)이고 $c$는 최소 총 감시 비용이다. 유효한 일정이 존재하지 않으면 대신 Case i: impossible을 출력한다.