Highway Patrol

A city has $N$ base stations connected by $M$ one-way highways. Highway $i$ runs from station $u_i$ to station $v_i$. To keep the city safe, every highway must be monitored in exactly one of two ways:

• Patrol it, at a cost of $p_i$, or
• Install video surveillance, at a cost of $s_i$.

The patrol schedule has to stay balanced: at every base station, the number of patrolled highways that leave the station must equal the number of patrolled highways that enter it. In other words, the set of patrolled highways must form a circulation, so each station has equal patrolled out-degree and in-degree.

For security reasons some highways must be patrolled: if $x_i = 1$, highway $i$ has to be patrolled; if $x_i = 0$, either monitoring method is allowed.

Video surveillance may not replace patrolling completely, so at least one highway must be patrolled.

Determine the minimum possible total monitoring cost, or report that no valid schedule exists.

The first line contains an integer $T$ ($1 \le T \le 70$), the number of test cases.

Each test case begins with a line containing two integers $N$ and $M$ ($1 \le N \le 100$, $1 \le M \le 1000$), the number of base stations and highways. Each of the next $M$ lines contains five integers $u$, $v$, $p$, $s$, $x$ ($1 \le u, v \le N$, $0 \le p, s \le 1000000$, $x \in {0, 1}$): a highway from station $u$ to station $v$ with patrol cost $p$, surveillance cost $s$, and $x = 1$ if the highway must be patrolled (otherwise $x = 0$).

For each test case print a line in the form Case i: c, where $i$ is the test case number (starting from $1$) and $c$ is the minimum total monitoring cost. If no valid schedule exists, print Case i: impossible instead.